1911. Maximum Alternating Subsequence Sum

Problem Description

The problem defines an alternating sum of an array as the sum of elements at even indices minus the sum of elements at odd indices. For instance, in an array [4,2,5,3], the alternating sum is (4 + 5) - (2 + 3) = 4.

The task is to find the maximum alternating sum of any subsequence in a given array nums. A subsequence can be obtained by deleting some elements (possibly none) from the original array but keeping the order of the remaining elements.

Intuition

To get the maximum alternating sum, we have to choose a subsequence where the difference between the sum of elements at even indices and the sum of elements at odd indices is maximized. This implies we want to include larger numbers at even indices and smaller numbers at odd indices, if possible.

To find the solution, we use dynamic programming to keep track of two values while iterating through the array: f and g. Here f represents the maximum alternating sum ending with an element at an even index, and g represents the maximum alternating sum ending with an element at an odd index.

When we are at a new number x, we have two choices: either include x in our subsequence or not. If the last included number was at an even index (and we are at an odd index now), f is updated by subtracting x from it, because we assume that including x would contribute to an alternating sum pattern. On the other hand, if we decide not to include x, then f remains the same. We choose the maximum of these two options to get the new value of f.
Similarly, when updating g (representing an odd index), we consider adding x (since we are now at an even index) to the previous g or keeping g as is. We select the maximum of these two choices.
As we loop through the array, f and g are updated in an alternating manner, reflecting the inclusion or exclusion of elements in the subsequence to maintain the pattern.
Finally, after considering all elements in nums, the maximum of f and g will be our answer, as it will represent the maximum alternating sum attainable by any subsequence of the original array.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem is elegantly handled with dynamic programming, where two variables f and g represent the current best alternating sums ending on an even index and an odd index, respectively. Here's a step-by-step breakdown of how the algorithm is implemented:

Initialization: We initialize two variables f and g to zero. Here, f will be used to track the maximum alternating sum ending with an even index, and g will track the maximum alternating sum ending with an odd index.
Iterating through nums: We loop through each element x in the provided array nums. For each element, we have to decide whether including it in the subsequence would lead to a higher alternating sum.
Dynamic Programming Transition:
- To update f, we take the maximum between the current value of f (which includes not picking x) and g - x (which accounts for picking x and adhering to the alternating sum rule). The equation can be written as f = max(f, g - x).
- To update g, we take the maximum between the current value of g (which also includes not picking x) and f + x (which accounts for picking x and maintaining the alternating pattern). The equation is g = max(g, f + x).
Maximizing the Result: With each element processed, the variables f and g are updated to always reflect the highest possible alternating sums up to that point.
Returning the Result: After the loop is finished, the larger of f and g will represent the largest alternating sum of a subsequence that can be formed from the array nums. Since the subsequence can end with either an even or odd indexed element, we take max(f, g) as the final result.

Using only two variables to keep track of the state at each step makes the solution space-efficient. The dynamic programming technique utilized here is especially useful as it avoids the need to consider all possible subsequences explicitly, which would be computationally expensive. The given implementation thus runs in O(n) time, where n is the number of elements in nums, since it processes each element only once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example using the array nums = [3, 1, 6, 4] to illustrate how the dynamic programming solution works with the given approach.

Initialization:
- Initialize f and g to zero.
- f (ends with even index) = 0
- g (ends with odd index) = 0
Element 1 (3 at index 0 which is even):
- To update f, we choose max between f (which is 0) and g - x (which is also 0 because g is 0).
- To update g, it remains 0, since 0 + 3 is less than f.
- Updated values: f = 3, g = 0
Element 2 (1 at index 1 which is odd):
- To update f, we choose max between f (which is 3) and g - x (which is -1, because g is 0 and x is 1).
- f doesn't change because 3 is greater than -1.
- To update g, we choose max between g (which is 0) and f + x (which is 4, because f is 3 and x is 1).
- Updated values: f = 3, g = 4
Element 3 (6 at index 2 which is even):
- To update f, we choose max between f (which is 3) and g - x (which is -2, because g is 4 and x is 6).
- f doesn't change because 3 is greater than -2.
- To update g, we choose max between g (which is 4) and f + x (which is 9, because f is 3 and x is 6).
- Updated values: f = 3, g = 9
Element 4 (4 at index 3 which is odd):
- To update f, we choose max between f (which is 3) and g - x (which is 5, because g is 9 and x is 4).
- Updated values: f = 5, g still 9, as f + x (which is 7) is less than g.

After considering all elements in nums, we have two final values for f and g. f holds the maximum alternating sum when we end on an even index and g when we end on an odd index.

f is 5
g is 9

The maximum between f and g is g. Therefore, the maximum alternating sum of any subsequence of the given array nums is 9.

This walkthrough captures the gradual update process of the dynamic programming approach where variables f and g facilitates the capture of the highest sums possible with alternating subsequence selection at every step without considering all subsequence combinations.

Solution Implementation

1from typing import List  # Import the List type from typing module for type hints.
2
3class Solution:
4    def max_alternating_sum(self, nums: List[int]) -> int:
5        even_index_sum = 0  # Initialize the max sum when considering even-indexed elements.
6        odd_index_sum = 0  # Initialize the max sum when considering odd-indexed elements.
7      
8        for num in nums:
9            # Calculate the new even_index_sum by considering the previous odd_index_sum
10            # and subtracting the current number (if it leads to a larger value).
11            new_even_index_sum = max(odd_index_sum - num, even_index_sum)
12          
13            # Calculate the new odd_index_sum by considering the previous even_index_sum
14            # and adding the current number (if it leads to a larger value).
15            new_odd_index_sum = max(even_index_sum + num, odd_index_sum)
16          
17            # Update the sums for the next iteration.
18            even_index_sum, odd_index_sum = new_even_index_sum, new_odd_index_sum
19      
20        # Return the maximum of both sums, determining the max alternating sum.
21        return max(even_index_sum, odd_index_sum)
22

1class Solution {
2    public long maxAlternatingSum(int[] nums) {
3        // Initialize the variables 'evenSum' and 'oddSum'.
4        // 'evenSum' tracks the maximum alternating sum ending with an element at an even index.
5        // 'oddSum' tracks the maximum alternating sum ending with an element at an odd index.
6        long evenSum = 0, oddSum = 0;
7      
8        // Iterate through the 'nums' array to calculate maximum alternating sums.
9        for (int num : nums) {
10            // 'nextEvenSum' will be the maximum of current 'oddSum' minus current 'num',
11            // or it will remain the same as the current 'evenSum'.
12            long nextEvenSum = Math.max(oddSum - num, evenSum);
13          
14            // 'nextOddSum' will be the maximum of current 'evenSum' plus current 'num',
15            // or it will remain the same as the current 'oddSum'.
16            long nextOddSum = Math.max(evenSum + num, oddSum);
17          
18            // Update 'evenSum' and 'oddSum' for the next iteration.
19            evenSum = nextEvenSum;
20            oddSum = nextOddSum;
21        }
22      
23        // Return the maximum of 'evenSum' and 'oddSum' as the result.
24        // It represents the maximum alternating sum that can be obtained.
25        return Math.max(evenSum, oddSum);
26    }
27}
28

1#include <vector>
2#include <algorithm> // Include algorithm header for 'max' function
3
4class Solution {
5public:
6    // Calculates the maximum alternating sum of an array.
7    long long maxAlternatingSum(vector<int>& nums) {
8        long long evenIndexSum = 0; // Sum when considering elements at even indices
9        long long oddIndexSum = 0;  // Sum when considering elements at odd indices
10      
11        // Loop through all elements in the array
12        for (int x : nums) {
13            // Update the sums at even and odd indices
14            long long newEvenIndexSum = max(oddIndexSum - x, evenIndexSum);
15            long long newOddIndexSum = max(evenIndexSum + x, oddIndexSum);
16          
17            // Assign the updated sums back to the variables for next iteration
18            evenIndexSum = newEvenIndexSum;
19            oddIndexSum = newOddIndexSum;
20        }
21      
22        // Return the maximum of the two sums
23        return max(evenIndexSum, oddIndexSum);
24    }
25};
26

1function maxAlternatingSum(nums: number[]): number {
2    // Introduce variables to keep track of alternating sums.
3    // oddSum: Sum when considering odd-indexed elements in the sequence.
4    // evenSum: Sum when considering even-indexed elements in the sequence.
5    let [evenSum, oddSum] = [0, 0];
6
7    // Iterate over each number in the nums array.
8    for (const num of nums) {
9        // Temporarily store the current state of evenSum,
10        // so we can update evenSum based on the prior value of oddSum.
11        let tempEvenSum = evenSum;
12
13        // Update evenSum: Choose the maximum between the current evenSum
14        // and (oddSum - current number) to simulate the effect of "adding" an even-indexed number.
15        evenSum = Math.max(oddSum - num, evenSum);
16
17        // Update oddSum by reversing the roles: Choose the maximum between the current oddSum
18        // and (evenSum + current number) to simulate the effect of "adding" an odd-indexed number.
19        oddSum = Math.max(tempEvenSum + num, oddSum);
20    }
21
22    // Return the maximum sum obtained by considering even-indexed elements.
23    // It represents the max alternating sum for the array.
24    return oddSum;
25}
26

Time and Space Complexity

The given Python code snippet defines a function that calculates the maximum alternating sum of an array. To analyze its time and space complexity, consider the following:

Time Complexity:

The function iterates through the list of numbers once. Let n be the length of nums.
Within this single loop, it performs constant-time operations such as computing the maximum value between two numbers and summing or subtracting x from the variables f and g.
There are no nested loops or recursive calls that would increase the complexity.
Therefore, the time complexity is O(n).

Space Complexity:

The function uses a fixed number of integer variables f, and g irrespective of the input size.
No additional data structures are created that grow with the size of the input.
Hence, the space complexity of the function is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don’t know