连续子数组的最大和

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

image.png

思路：计数组的和，如果发现和小于0 就设置curSum为当前值，如果大于0 继续加

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length<= 0 ){
            return 0;
        }
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0;i<array.length;i++){
            if(curSum<0){
                curSum = array[i];
            }else{
                curSum += array[i];
            }
            maxSum = maxSum>curSum?maxSum:curSum;
        }
        return maxSum;
    }
}

也可推出偏移公式 dp[i] = Math.max( dp[i-1]+array[i],array[i]);