2036. Maximum Alternating Subarray Sum (kadane-algo)

T: o(n)
S: o(1)

max 0's timing is different for Leetcode 53

class Solution {
 // 有兩種可能, 偶數位出發和odd位出發, 所以做  twice Kadane
    public long maximumAlternatingSubarraySum(int[] nums) {
        long result = Long.MIN_VALUE;
        long even = 0;
        long odd = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) { // 從偶數位開始當第一個, 所以是 +
                even = Math.max(nums[i], even + nums[i]);
                // add 後, 如果反而比較小, 就丟棄之前的 sum(even), 保留目前的數(nums[i])開始累加
            } else {
                even = Math.max(0, even - nums[i]); // use [2,2,2,2,2] example , so we can't use Math.max(nums[i], even - nums[i]); it'll make number larger
                // in substraction case, only check is it become negative
                // 如果減掉目前的數後, < 0, 那整個都丟掉, 直接從 0 開始 （因為目前的數是要剪法的, 所以保留(nums[i])並沒有用）
            }
            result = Math.max(result, even);
        }
        for (int i = 1; i < n; i++) {
            if (i % 2 == 1) { // 從odd數位開始當第一個, 所以是 +
                odd = Math.max(nums[i], odd + nums[i]);
            } else {
                odd = Math.max(0, odd - nums[i]);
            }
            result = Math.max(result, odd);
        }
        return result;
    }
}

/*
[3,-1,1,2]
 + - +  -
   + -  + 
   
// pure kadane
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;
    }
}

// do twice Kadane
// because there are 2 condition
// one is start from even digit(+-+-), until now find max, got start from even's max
// one is start from odd digit(+-+), find max with even's max, max(oddmax, evenmax) -> this is the ans
[3,-1,1,2]
 + - +  -
   + -  + 
   
T: o(n)
S: o(1)
*/