剑指offer-30-连续子数组的最大和

思路

求连续某一段和，即求累积和，sum[i]表示从0-i的累积和
累计和的最大与最小值之差即为连续最大和，但是要处理一种特殊情况，即数据全为负数

代码

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){return 0;}
        int[] sum=new int[array.length+1];
        int max=0,min=Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++){
            sum[i+1]+=sum[i]+array[i];
            min=Math.max(min,array[i]);
        }
        if(min<0){return min;}
        for(int i=0;i<sum.length;i++){
            min=Math.min(min,sum[i]);
            max=Math.max(max,sum[i]-min);

        }
        return max;
    }
}