面试题43：连续子数组的最大和

{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

动态规划。时间复杂度：O(n)，空间复杂度：O(n)

1. 若数组长度为1，直接返回；
2. 若数组长度大于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;
}