最大子数组和

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array == null || array.length == 0) return 0;
        return subArray(array,0,array.length-1);
    }
    
    int subArray(int[] a, int left, int right){
        if(left == right){
            return a[left];
        } // 递归终止条件
        int mid = (left+right) >>> 1;
        // 递归向下，知道左右指针重合，表示划分结束
        int leftVal = subArray(a,left,mid);
        int rightVal = subArray(a,mid+1,right);
        
        // 合并：找到包含中间两个数的最大值
        int max = Math.max(leftVal,rightVal);
        int sum = 0;
        for(int i=mid;i>=0;i--){
            sum += a[i];
            max = Math.max(sum,max);
        }
        for(int i=mid+1;i<=right;++i){
            sum += a[i];
            max = Math.max(sum,max);
        }
        return max;
    }
}

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = Integer.MIN_VALUE;
        int[] dp = new int[array.length];
        dp[0] = array[0];
        for(int i=1;i<array.length;i++){
            if(array[i] > dp[i-1]+array[i]){
                dp[i] = array[i]; // 丢弃之前的和
            }else {
                dp[i] = dp[i-1] + array[i]; // 在之前的和上累加
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }
}