连续子数组的最大和

设dp[i]表示0..i以i结尾的连续子数组的最大序列和，那么有如下状态公式：

1. 当i=0时，dp[0] = arr[0]
2. 当i>0时，dp[i] = max(dp[i], dp[i]+arr[i-1])

代码如下：

//
// Created by jt on 2020/9/18.
//
#include <vector>
using namespace std;

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if (array.size() < 1) return 0;
        vector<int> dp(array.size(), 0);
        dp[0] = array[0];
        int res = dp[0];
        for (int i = 1; i < array.size(); ++i) {
            dp[i] = max(array[i], array[i] + dp[i-1]);
            res = max(res, dp[i]);
        }
        return res;
    }
};