题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
- 动态规划 状态 转移方程： 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; } };
