We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Absolute Sum of Any Subarray

Number: 1849

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft

Problem Description

Given an integer array, the task is to compute the maximum absolute sum of any (possibly empty) subarray. The absolute sum of a subarray is defined as the absolute value of the sum of its elements. Empty subarray sums to 0, so the answer is always at least 0.

Key Insights

  • The problem can be reduced to finding two quantities: the maximum subarray sum and the minimum subarray sum.
  • The maximum absolute sum will be the maximum of these two values, since taking the absolute ensures both positive and negative extremes are accounted for.
  • Kadane’s algorithm can be used to efficiently find both the maximum subarray sum and the minimum subarray sum in O(n) time.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1), since only a constant amount of extra space is used.

Solution

The solution uses Kadane's algorithm twice. First, we calculate the maximum subarray sum by iteratively updating the current maximum and overall maximum. Then, we can modify the algorithm to get the minimum subarray sum by tracking the current minimum and overall minimum. The answer is then the maximum of the overall maximum and the absolute value of the overall minimum. This approach is efficient and uses constant extra space.

Code Solutions

# Python solution using Kadane's algorithm for both max and min subarray sums.
def maxAbsoluteSum(nums):
    # Initialize variables for the maximum subarray sum
    max_ending_here = 0
    max_sum = 0
    
    # Initialize variables for the minimum subarray sum
    min_ending_here = 0
    min_sum = 0
    
    # Iterate over each number in the list
    for num in nums:
        # Update the maximum sum subarray ending at current position
        max_ending_here = max(0, max_ending_here + num)
        max_sum = max(max_sum, max_ending_here)
        
        # Update the minimum sum subarray ending at current position
        min_ending_here = min(0, min_ending_here + num)
        min_sum = min(min_sum, min_ending_here)
    
    # The maximum absolute sum is the maximum of the absolute min sum and max sum
    return max(max_sum, abs(min_sum))

# Example usage:
nums = [1, -3, 2, 3, -4]
print(maxAbsoluteSum(nums))  # Output: 5
← Back to All Questions