JZ30-连续子数组的最大和

class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int len = array.length;
        int[] dp = new int[len];

        int max = array[0];
        dp[0] = array[0];

        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(array[i], dp[i - 1] + array[i]); //如果a[i]更大，就直接舍弃之前的数列，重新开始新的一段。
            max = Math.max(dp[i], max); //然后记录每一段的最大值
        }
        return max;
    }
}

class Solution2 {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int val : array) {
            if (sum <= 0) { //val+一个负数会更小，所有选较大的val//重新开一段
                sum = val;
            } else {  //val+ 一个正数会更大，所有选较大的val + sum
                sum = val + sum;
            }
            max = Math.max(sum, max); //记录当前最大值。相当于swap了。
        }
        return max;
    }
}