题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
归为简单题是有道理的，算是一个最简单的的动态规划问题。
问题的关键是最大子数组和的问题拆解，可以拆解为以数组任意位置结尾的子数组的最大和。
以当前位置的结尾的子数组最大和跟前一个位置结尾的子数组的最大和的关系是：
1.连接前一个位置：
dp[i-1]+array[i]
2.不连接前一个位置
array[i]
求最大值作为以当前位置结尾的最大值。
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() == 0){
return 0;
}
vector<int> dp = {array[0]};
int res = array[0];
for(int i=1;i<array.size();i++){
dp[i] = max(dp[i-1]+array[i],array[i]);
res = max(res,dp[i]);
}
return res;
}
};
查看14道真题和解析