1749. Maximum Absolute Sum of Any Subarray

MediumView on LeetCode

Array Dynamic Programming

Time: O(n)

Space: O(1)

Intuition

Maximum absolute sum of any subarray. Max of (maximum subarray sum) and (absolute of minimum subarray sum).

Algorithm

1Run Kadane for maximum subarray sum.
2Run Kadane for minimum subarray sum.
3Return max(max_sum, abs(min_sum)).

Common Pitfalls

•|sum| is maximized by either the most positive or most negative subarray.

1749.cs

// Approach: Track max prefix sum and min prefix sum; answer is max(maxSum, -minSum).
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxAbsoluteSum(int[] nums)
    {
        int ans = int.MinValue;
        int maxSum = 0;
        int minSum = 0;

        foreach (int num in nums)
        {
            maxSum = Math.Max(num, maxSum + num);
            minSum = Math.Min(num, minSum + num);
            ans = Math.Max(ans, Math.Max(maxSum, -minSum));
        }

        return ans;
    }
}

Was this solution helpful?