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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Alternating Subarray Sum

Number: 512

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed integer array, an alternating subarray is defined as a contiguous non-empty sequence where the elements are added and subtracted in an alternating pattern, starting with addition. For any subarray from index i to j, its alternating sum is computed as nums[i] - nums[i+1] + nums[i+2] - ... (with the appropriate sign for the last element). The task is to find the maximum alternating subarray sum among all possible subarrays.

Key Insights

  • The alternating sum can be computed with a dynamic programming approach where at each index we track the maximum sum ending at that index when the index contributes positively (even position in the alternating pattern) and when it contributes negatively (odd position).
  • We can restart a subarray at any index, treating that element as the start (with a positive sign).
  • By maintaining only the previous state (even and odd sums), the solution can be computed in O(n) time and O(1) space.
  • A careful initialization is required since the first element always starts as a positive contribution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We maintain two variables:

  1. dp_even – the maximum alternating subarray sum ending at the current index where the current element is added.
  2. dp_odd – the maximum alternating subarray sum ending at the current index where the current element is subtracted.

For the first element: • dp_even = nums[0] (since the subarray containing only nums[0] contributes nums[0]) • dp_odd is initialized to negative infinity because we haven't performed a subtraction yet.

For each subsequent index i: • To update dp_even (the sum if nums[i] is added), we can either start a new subarray at position i (which gives a sum of nums[i]) or extend a previous subarray that ended with a subtraction by adding the current element (dp_odd + nums[i]). • To update dp_odd (the sum if nums[i] is subtracted), we can only extend a subarray which previously ended with an addition (dp_even - nums[i]).

The overall answer is the maximum dp_even over all indices since valid subarrays must start with a positive sign.

Code Solutions

# Python solution using dynamic programming

def maxAlternatingSum(nums):
    # Initialize dp_even with the first element
    dp_even = nums[0]
    # Initialize dp_odd as negative infinity as no subtraction has occurred yet
    dp_odd = float('-inf')
    # Maximum alternating sum found so far
    max_sum = dp_even
    
    # Iterate from the second element to the end
    for i in range(1, len(nums)):
        # If we want the current index to contribute positively,
        # we can either start a new subarray at nums[i] or extend a previous subarray ending with dp_odd.
        new_even = max(nums[i], dp_odd + nums[i])
        
        # If we want to subtract the current number, we extend the subarray ending with dp_even.
        new_odd = dp_even - nums[i]
        
        # Update dp_even and dp_odd for the current index
        dp_even, dp_odd = new_even, new_odd
        
        # Update the maximum alternating sum found so far
        max_sum = max(max_sum, dp_even)
    
    return max_sum

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