解题思路:
- 当前位置的元素是否要和前面连接起来,取决于前一个位置的连续最大值。
- 如果前面位置的连续最大值已经小于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; } }