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 includex
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 subtractingx
from it, because we assume that includingx
would contribute to an alternating sum pattern. On the other hand, if we decide not to includex
, thenf
remains the same. We choose the maximum of these two options to get the new value off
. -
Similarly, when updating
g
(representing an odd index), we consider addingx
(since we are now at an even index) to the previousg
or keepingg
as is. We select the maximum of these two choices. -
As we loop through the array,
f
andg
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 off
andg
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
andg
to zero. Here,f
will be used to track the maximum alternating sum ending with an even index, andg
will track the maximum alternating sum ending with an odd index. -
Iterating through nums: We loop through each element
x
in the provided arraynums
. 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 off
(which includes not pickingx
) andg - x
(which accounts for pickingx
and adhering to the alternating sum rule). The equation can be written asf = max(f, g - x)
. - To update
g
, we take the maximum between the current value ofg
(which also includes not pickingx
) andf + x
(which accounts for pickingx
and maintaining the alternating pattern). The equation isg = max(g, f + x)
.
- To update
-
Maximizing the Result: With each element processed, the variables
f
andg
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
andg
will represent the largest alternating sum of a subsequence that can be formed from the arraynums
. Since the subsequence can end with either an even or odd indexed element, we takemax(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 EvaluatorExample 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
andg
to zero. f
(ends with even index) = 0g
(ends with odd index) = 0
- Initialize
-
Element 1 (3 at index 0 which is even):
- To update
f
, we choose max betweenf
(which is 0) andg - x
(which is also 0 becauseg
is 0). - To update
g
, it remains 0, since 0 + 3 is less than f. - Updated values:
f
= 3,g
= 0
- To update
-
Element 2 (1 at index 1 which is odd):
- To update
f
, we choose max betweenf
(which is 3) andg - x
(which is -1, becauseg
is 0 andx
is 1). f
doesn't change because 3 is greater than -1.- To update
g
, we choose max betweeng
(which is 0) andf + x
(which is 4, becausef
is 3 andx
is 1). - Updated values:
f
= 3,g
= 4
- To update
-
Element 3 (6 at index 2 which is even):
- To update
f
, we choose max betweenf
(which is 3) andg - x
(which is -2, becauseg
is 4 andx
is 6). f
doesn't change because 3 is greater than -2.- To update
g
, we choose max betweeng
(which is 4) andf + x
(which is 9, becausef
is 3 andx
is 6). - Updated values:
f
= 3,g
= 9
- To update
-
Element 4 (4 at index 3 which is odd):
- To update
f
, we choose max betweenf
(which is 3) andg - x
(which is 5, becauseg
is 9 andx
is 4). - Updated values:
f
= 5,g
still 9, asf + x
(which is 7) is less thang
.
- To update
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 5g
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 ofnums
. - 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 variablesf
andg
. - 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
, andg
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.
What's the relationship between a tree and a graph?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.