Question link on leetcode: Leetcode

Intuition

Maximum subarray sum: Kadane’s algorithm

Approach

Take two sums, Max subarray sum and Min subarray sum.
Use Kadane’s algorithm to find both.
In the last, compare the max sum and min absolute sum and return the max between them.

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

Code

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int minSum = Integer.MAX_VALUE;
        int currMax = 0;
        int currMin = 0;
        for(int num: nums){
            currMax +=num;
            currMin +=num;
            maxSum = Math.max(maxSum,currMax);
            minSum = Math.min(minSum,currMin);
            if(currMax<0) currMax = 0;
            if(currMin>0) currMin = 0;
        }
        return Math.max(maxSum,Math.abs(minSum));
    }
}

Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

原文链接：Maximum Absolute Sum of Any Subarray LC – 1749