动态规划

方法1，可以通过暴力On^2的方法，循环两次求出每个子数组的和对比。

法2.DP

设dp[i]，dp[i]代表以array[i]为结尾的连续子数组最大和。 转移方程为，dp[i] = max(array[i]，dp[i-1] + array[i])，理解如下：

• 因为以第n个数为结尾，所以array[n]是必然被选择的
• 基于dp[n-1]的值，如果dp[n-1]>0，我们加上这个正数，值必然会增大
• 如果dp[n-1]<0,那么加上负数，值就会减小，不如不要前面的结果，只要当前这个数，结果反而更优。

#include <vector>
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if(array.size() == 1) return array.front();
        int res = array.front();
        vector<int> dp;
        dp.resize(array.size() + 10, 0);
        
        dp[0] = array.front();

        for(int i = 1; i<array.size(); ++i){
            dp[i] = max(array[i], dp[i-1] + array[i]);
            res = max(dp[i], res);
        }
        
        return res;

    }
};