53. Maximum Subarray (kadane-algo

T: O(n)

S: O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, sum);
            sum = Math.max(0, sum); // [-1] -> should remain [-1], so put here
        }
        return max;
    }
}

or

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            // sum += num;
            // add 後, 如果反而比較小, 就丟棄之前的 sum
            sum = Math.max(sum + num, num); // [-1] -> should remain [-1], so put here
            max = Math.max(max, sum);
            
        }
        return max;
    }
}