题解 | #连续子数组的最大和#

1. 动态规划 状态 转移方程： d[i] = max(d[i],d[i-1]+arr[i-1]) max(ret,d[i])

class Solution { public: int FindGreatestSumOfSubArray(vector array) { vector dp(array.size()+1, 0); dp[0] = 0; // 表示没有元素 int ret = array[0]; for (int i=1; i<=array.size(); ++i) { dp[i] = max(array[i-1], dp[i-1]+array[i-1]); ret = max(ret, dp[i]); } return ret; } };