连续子数组的最大和_JAVA_简单

• 求最大连续子数组和 可以转化为 求以每一个元素结尾的最大子数组和的最大值，而以当前元素结尾的最大子数组和可以由以上一个元素结尾的最大子数组和求得，则可使用动态规划qiuj
• 设n为当前遍历元素下标，e为当前元素，f(n)为以当前元素结尾的子数组和最大值，则f(n) = MAX(f(n - 1) + e, e)，则最大子数组和为计算出的f(n)的最大值

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int nowSum = 0, maxSum = Integer.MIN_VALUE;

        for(int e : array) {
            // 以当前元素为结尾的数组最大和 即为 MAX（当前元素+前一个元素为结尾的最大和，当前元素）
            nowSum = nowSum > 0 ? nowSum + e : e;

            // 更新当前累加值后也更新最大累加值
            maxSum = maxSum >= nowSum ? maxSum : nowSum;
        }

        return maxSum;
    }
}