题解 | #连续子数组的最大和#(动态规划)
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
算法思路（动态规划）
- 设dp[n]为以第n个数为结尾，得到的子数组的和的最大值，因为以第n个数为结尾所以array[n]是必然被选择的。
- 基于dp[n-1]的值，如果dp[n-1]>0，我们加上这个正数，我们的值是不是必然会增大；如果dp[n-1]<0,那么我们加上负数，我们的值就会减小，这个时候我们不如不要前面的结果，只要当前这个数，结果反而更优。
- 于是我们就得到了状态转移方程dp[n]=array[n]+(dp[n-1]>0?dp[n-1]:0)，实时跟ans比较，更新最大值即可。
代码实现
当然对这一道题来说，我们不用定义一个dp数组，而只定义一个now变量来代替dp数组，如果now<0，那么就令now=array[i]。如果now>0，那么就令now+=array[i]。
//典型的动态规划题
class Solution
{
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
//now代表各个状态，ans保留最大的那个状态。
int now, ans;
now = 0, ans = INT_MIN;
for (int i = 0; i < array.size(); i++)
{
if (now < 0)//now<0,则舍去前面的
now = array[i];
else
{
now += array[i];//比0大则直接加上去
}
ans = max(now, ans);//更新ans
}
return ans;
}
};
查看10道真题和解析