解题思路:

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