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 Alternating Subsequence Sum

Number: 2022

Difficulty: Medium

Paid? No

Companies: Quince

Problem Description

Given an array of positive integers, find a subsequence (which can be derived by deleting zero or more elements without disturbing the order) such that the alternating sum of the subsequence is maximized. The alternating sum is calculated by summing the elements at even indices (after reindexing the subsequence) and subtracting the sum of the elements at odd indices.

For example, the alternating sum of [4,2,5,3] is (4+5) - (2+3) = 4. You are to return the maximum alternating sum obtainable from any subsequence of the input array.

Key Insights

  • The alternating sum depends only on the order of the selected numbers, not on their original indices.
  • At every element in the array, we decide whether to include it or not to maximize the alternating sum.
  • We can use Dynamic Programming by keeping track of two states:
    • The best alternating sum when the current element would be placed at an even index (added to the sum).
    • The best alternating sum when the current element would be placed at an odd index (subtracted from the sum).
  • These two states can be updated iteratively in one pass through the array.

Space and Time Complexity

Time Complexity: O(n) where n is the size of the input array. Space Complexity: O(1) as we only use two variables to maintain the states.

Solution

We use a Dynamic Programming approach with two state variables:

  • even_sum: The maximum alternating sum ending with an “addition” (even index).
  • odd_sum: The maximum alternating sum ending with a “subtraction” (odd index).

Initially, both even_sum and odd_sum are set to 0 (representing an empty subsequence or subsequences that start with a single element).

For each number x in the array, we compute:

  • even_sum = max(even_sum, odd_sum + x)
    • This determines whether adding x to a sequence ending with a subtraction yields a higher alternating sum or if we simply keep the previous even_sum.
  • odd_sum = max(odd_sum, even_sum - x)
    • This determines whether subtracting x from a sequence ending with an addition is beneficial.

At the end of the traversal, even_sum holds the maximum alternating sum over all subsequences. This works because the best possible sequence should always end in the addition phase to maximize the value.

Code Solutions

# Python solution for Maximum Alternating Subsequence Sum

def maximum_alternating_sum(nums):
    # even_sum represents the maximum alternating sum ending on an even (addition) index
    # odd_sum represents the maximum alternating sum ending on an odd (subtraction) index
    even_sum = 0  # starting with an empty subsequence which gives a sum of 0
    odd_sum = 0   # initially no subtraction has been made
    
    # Iterate over each number in the array
    for num in nums:
        # Calculate potential new sum if we add the current number after an odd position
        new_even = max(even_sum, odd_sum + num)
        # Calculate potential new sum if we subtract the current number after an even position
        new_odd = max(odd_sum, even_sum - num)
        
        # Update the sums for the next iteration
        even_sum, odd_sum = new_even, new_odd
    
    # The answer is the maximum alternating sum ending with addition (even index)
    return even_sum

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