Description
给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。
Input
第一行有一个正整数n(n<1000),后面跟n个整数,绝对值都小于10000。直到文件结束。
Output
输出它的最大子段和。
Sample Input
6 -2 11 -4 13 -5 -2
Sample Output
20
参考: https://blog.csdn.net/niteip/article/details/7444973#
-
穷举法 时间复杂度:$O(n^3)$
/*O(n^3)*/ #include <stdio.h> #include <stdlib.h> int main() { int n; int num[1001]; int i, j, k; int sum, max; while (~scanf("%d", &n)) { for (i = 0; i < n; i++) scanf("%d", &num[i]); max = 0; for (i = 0; i < n; i++) { for (j = i; j < n; j++) { sum = 0; for (k = i; k <= j; k++) sum += num[k]; if (sum > max) max = sum; } } printf("%d ", max); } return 0; }
-
穷举法
时间复杂度:$O(n^2)$
/*O(n^2)*/ #include <stdio.h> #include <stdlib.h> int main() { int n; int num[1001]; int i, j, k; int sum, max; while (~scanf("%d", &n)) { for (i = 0; i < n; i++) scanf("%d", &num[i]); max = 0; for (i = 0; i < n; i++) { sum = 0; for (j = i; j < n; j++) { sum += num[j]; if (sum > max) max = sum; } } printf("%d ", max); } return 0; }
-
分治法
时间复杂度:$O(nlog_2n)$
/*O(nlogn)分治法*/ #include <iostream> #include <cstdio> #include <cstdlib> int maxSubSegSum(int num[], int left, int right) { int mid = (left + right) / 2; if (left == right) return num[left] > 0 ? num[left] : 0; int leftMaxSum = maxSubSegSum(num, left, mid); int rightMaxSum = maxSubSegSum(num, mid + 1, right); int sum = 0; int leftSum = 0; for (int i = mid; i >= left; i--) { sum += num[i]; if (sum > leftSum) leftSum = sum; } sum = 0; int rightSum = 0; for (int i = mid + 1; i <= right; i++) { sum += num[i]; if (sum > rightSum) rightSum = sum; } int retSum = leftSum + rightSum; if (retSum < leftMaxSum) retSum = leftMaxSum; if (retSum < rightMaxSum) retSum = rightMaxSum; return retSum; } int main() { int n; int num[1001]; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) scanf("%d", &num[i]); printf("%d ", maxSubSegSum(num, 0, n - 1)); } return 0; }
-
动态规划
时间复杂度:$O(n)$
/*O(n) 动态规划*/ #include <stdio.h> #include <stdlib.h> #include <memory.h> int main() { int n; int num[1001]; int f[1001 + 1]; int i; int max; while (~scanf("%d", &n)) { for (i = 1; i <= n; i++) scanf("%d", &num[i]); max = 0; memset(f, 0, sizeof(f)); for (i = 1; i <= n; i++) { if (f[i - 1] > 0) f[i] = f[i - 1] + num[i]; else f[i] = num[i]; if (f[i] > max) max = f[i]; } printf("%d ", max); } return 0; }
或者
/*O(n) 动态规划*/ #include <stdio.h> #include <stdlib.h> #include <memory.h> int main() { int n; int num[1001]; int b; int i; int max; while (~scanf("%d", &n)) { for (i = 1; i <= n; i++) scanf("%d", &num[i]); max = 0; b = 0; for (i = 1; i <= n; i++) { b = b > 0 ? b + num[i] : num[i]; max = b > max ? b : max; } printf("%d ", max); } return 0; }