贪心

class Solution {
    public int maxSubArray(int[] nums) {

        /**
         * 元素中有负数，因此max初始值取负数最小值
         */
        int max = -Integer.MAX_VALUE;
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            sum += nums[i];

            /**
             * 每次得到一个新的和，都要更新一下最大值
             */
            if (sum > max){
                max = sum;
            }

            /**
             * 如果加上nums[i]导致结果变负了或者为0，说明这段区间不会带来正收益了
             * 直接清空累加，从下一个元素开始
             */
            if (sum < 0){
                sum = 0;
            }
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/assign-cookies/