本文共 560 字，大约阅读时间需要 1 分钟。
一个数组中，既有正数，也有负数，计算出他的子数组和的最大值。
思路：
我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和 可能为 max( dp[ i -1 ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n#includeusing namespace std;int GetMax(int a, int b){ return a > b ? a : b;}int FindMaxSum(int a[],int N){ int sum = a[0]; int max = a[0]; for (int i = 1; i < N; i++) { sum = GetMax(sum + a[i], a[i]); if (sum >= max) max = sum; } return max;}int main(){ int a[] = { 1, 4, -3, 6, 2 }; int N = sizeof(a) / sizeof(a[0]); FindMaxSum(a, N); return 0;}
转载地址：http://axuoi.baihongyu.com/