题解 | #连续子数组的最大和#
连续子数组的最大和
http://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484
解题思路：
- 当前位置的元素是否要和前面连接起来，取决于前一个位置的连续最大值。
- 如果前面位置的连续最大值已经小于0了，那么没有必要再和它连在一起了，自己重新开始一个序列即可。
代码实现：
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
//1.初始值
dp[0] = array[0];
//2.转移方程 dp[i] = Math.max(dp[i-1], 0) + array[i];
int max = dp[0];
for(int i=1; i<array.length; i++){
dp[i] = Math.max(dp[i-1], 0) + array[i];
max = Math.max(max, dp[i]);
}
return max;
}
}
查看15道真题和解析
