JZ_30连续子数组的最大和.md

JZ_30连续子数组的最大和

动态规划：令dp[i]为以array[i]结尾的最大连续子数组，显然动态转移方程为dp[i] = max(dp[i-1] + array[i], array[i])，如果和前一个的和大于单独一个则并入前一个连续子数组，直到i = len-1，最后遍历一遍dp[i]，因为最大连续子数组一定是由某个array[i]结尾的连续子数组

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array.length == 0) return 0;
        int len = array.length;
        int[] dp = new int[len];
        //dp[i]为以i元素结尾的最大的情况，显然，最大连续子序列必然是以某一个元素结尾的
        dp[0] = array[0];
        for (int i = 1; i < len; i++)
            //以编号为i的元素结尾的连续子序列的最大值可能是前一个序列+array[i],又或者是单独成一个序列
            dp[i] = dp[i-1] + array[i] > array[i] ? dp[i-1] + array[i] : array[i];
        //按照补码的值，1左移31位后结果是-2^31
        int max = 1<<31;
        for (int i = 0; i < len; i++)
            //如果dp[i]更大则赋给max
            max = max < dp[i] ? dp[i] : max;
        return max;
    }
}