设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;
    }
};