设dp[i]表示0..i
以i结尾的连续子数组的最大序列和,那么有如下状态公式:
- 当i=0时,dp[0] = arr[0]
- 当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; } };