{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
动态规划。时间复杂度：O(n)，空间复杂度：O(n)
- 若数组长度为1，直接返回；
- 若数组长度大于1，则根据公式算出数组每个位置的最大连续子序列的和。
i=0,maxSum[0]=array[0]=6;
i=1,maxSum[1]=max(array[1],array[1]+maxSum[0])=max(-3,-3+6)=3;
i=2,maxSum[2]=max(array[2],array[2]+maxSum[1])=max(-2,-2+3)=1;
......
状态转移方程：maxSum[i]=max(array[i],array[i]+maxSum[i-1]);
#include <iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
vector<int> maxSum;
int FindGreatestSumOfSubArray(vector<int> array) {
if (array.size() == 0)
return 0;
maxSum.push_back(array[0]);
for (int i = 1; i < array.size(); i++)
{
int maxsum = max(array[i], array[i] + maxSum[i - 1]);
maxSum.push_back(maxsum);
}
sort(maxSum.begin(), maxSum.end(), greater<int>());
return maxSum[0];
}
int main()
{
vector<int> array = { 6,-3};
cout << FindGreatestSumOfSubArray(array) << endl;
return 0;
}
