求最大子数组和的算法

求最大子数组和的算法2015-02-15比如对于数组[1,-2,3,5,-1,2] 最大子数组和是sum[3,5,-1,2] = 9, 我们要求函数输出子数组和的最大值,并且返回子数组的左右边界（下面函数的left和right参数）.

本文我们规定当数组中所有数都小于0时，返回数组中最大的数（也可以规定返回0，只要让以下代码中maxsum初始化为0即可，此时我们要注意-1 0 0 0 -2这种情形，特别是如果要求输出子数组的起始位置时，如果是面试就要和面试官问清楚）

以下代码我们在PAT 1007. Maximum Subsequence Sum测试通过,测试main函数如下

int main（）{int n;scanf（"%d", &n）;vector<int>vec（n）;for（int i = 0; i < n; i++）scanf（"%d", &vec[i]）;int left, right;int maxsum = maxSum1（vec, left, right）;//测试时替换函数名称if（maxsum >= 0）printf（"%d %d %d", maxsum, vec[left], vec[right]）;else printf（"0 %d %d", vec[0], vec[n-1]）;}

参考：编程之美2.14 求数组的子数组之和的最大值

算法1：最简单的就是穷举所有的子数组，然后求和，复杂度是O（n^3）

int maxSum1（vector<int>&vec, int &left, int &right）{int maxsum = INT_MIN, sum = 0;for（int i = 0; i < vec.size（）; i++）for（int k = i; k < vec.size（）; k++）{sum = 0;for（int j = i; j <= k; j++）sum += vec[j];if（sum > maxsum）{maxsum = sum;left = i;right = k;}}return maxsum;}

算法2: 上面代码第三重循环做了很多的重复工作,稍稍改进如下,复杂度为O（n^2）

int maxSum2（vector<int>&vec, int &left, int &right）{int maxsum = INT_MIN, sum = 0;for（int i = 0; i < vec.size（）; i++）{sum = 0;for（int k = i; k < vec.size（）; k++）{sum += vec[k];if（sum > maxsum）{maxsum = sum;left = i;right = k;}}}return maxsum;}