题解 | 连续子数组的最大和

import java.util.*;

public class Solution {
    /**
     * 贪心：只要当前正在连续累加的子数组和>0，就继续连接。然后当遇到峰值的时候记录下来
     */
    public int FindGreatestSumOfSubArray (int[] array) {    
        // 记录全局出现过的最大子数组和
        int maxAns = array[0];
        
        // 记录当前正在连续累加的子数组和（也是我们的贪心核心指标）
        int curSum = array[0];

        for (int i = 1; i < array.length; i++) {
            // 局部最优选择：如果之前的累加和 curSum 已经是负数（负债）了，
            // 那么丢弃它，直接从当前数字 array[i] 重新开始算起点。
            if (curSum < 0) {
                curSum = array[i];
            } else {
                // 如果之前的累加和 curSum 是正数（资产），哪怕当前 array[i] 是负数，也可以接着连
                curSum += array[i];
            }

            // 每次更新完当前连续和，都要贪心地去和全局最大值比一下，记录下历史最高峰
            maxAns = Math.max(curSum, maxAns);
        }

        return maxAns;
    }
}