DDSA Solutions

1749. Maximum Absolute Sum of Any Subarray

MediumView on LeetCode
ArrayDynamic Programming
Time: O(n)
Space: O(1)

Problem Overview

Maximum absolute sum of any subarray.

Intuition

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

Algorithm

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

Common Pitfalls

  • •|sum| is maximized by either the most positive or most negative subarray.
1749.cs
C#
// 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?

Related Problems