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

Difficulty: Medium

Problem Description

The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices. Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).

Key Insights

  • The problem requires maximizing the difference between the sum of selected even-indexed elements and the sum of selected odd-indexed elements.
  • A subsequence can be formed by deleting some elements while maintaining the relative order of the remaining elements.
  • Dynamic programming can be utilized to keep track of the best possible sums at each step.

Space and Time Complexity

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

Solution

We can solve this problem using a dynamic programming approach. The idea is to maintain two variables to represent the maximum alternating sum up to the current index: one for the sum including the current element (considered as even) and another for the sum excluding the current element (considered as odd). As we iterate through the array, we update these values based on whether we include the current element or not.

Code Solutions

def maxAlternatingSum(nums):
    even_sum = 0
    odd_sum = 0
    
    for num in nums:
        even_sum = max(even_sum, odd_sum + num)  # Include the current number in the even sum
        odd_sum = max(odd_sum, even_sum - num)   # Include the current number in the odd sum
    
    return even_sum

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