题解 | #连续子数组的最大和#

最简单的理解就是，dp[i-1]是正数或0，就可以继续累积子数组；是负数，就记录下最大值，下一个元素重新判断。

因为一旦是负数，不管后面加任何数都会让和减小，所以只要之前的和出现负数，就可以从新开始计算子数组了。

其实整理下和官方题解的工公式是一样，但是这样说就很好理解

 public int FindGreatestSumOfSubArray (int[] array) {
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];
        for(int i=1;i<array.length;i++){
            // 动态规划，状态转移方程，确定dp[i]的最大值
            if(dp[i-1]>=0){
                dp[i]=dp[i-1]+array[i];

            }else dp[i]=array[i];//以array[i]为第一个元素重新计算子数组
            // 每次比较，保存出现的最大值
            max = Math.max(max,dp[i]);
        }
        return max;
    }