1911. Maximum Alternating Subsequence Sum LeetCode Solution

In this guide, you will get 1911. Maximum Alternating Subsequence Sum LeetCode Solution with the best time and space complexity. The solution to Maximum Alternating Subsequence Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Alternating Subsequence Sum solution in C++
Maximum Alternating Subsequence Sum solution in Java
Maximum Alternating Subsequence Sum solution in Python
Additional Resources

1911. Maximum Alternating Subsequence Sum LeetCode Solution image

Problem Statement of Maximum Alternating Subsequence Sum

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.

For example, the alternating sum of [4,2,5,3] is (4 + 5) – (2 + 3) = 4.

Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: nums = [4,2,5,3]
Output: 7
Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) – 2 = 7.

Example 2:

Input: nums = [5,6,7,8]
Output: 8
Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.

Example 3:

Input: nums = [6,2,1,2,4,5]
Output: 10
Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) – 1 = 10.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 105

Complexity Analysis

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

1911. Maximum Alternating Subsequence Sum LeetCode Solution in C++

class Solution {
 public:
  long long maxAlternatingSum(vector<int>& nums) {
    long even = 0;  // the maximum alternating sum ending in an even index
    long odd = 0;   // the maximum alternating sum ending in an odd index

    for (const int num : nums) {
      even = max(even, odd + num);
      odd = even - num;
    }

    return even;
  }
};
/* code provided by PROGIEZ */

1911. Maximum Alternating Subsequence Sum LeetCode Solution in Java

class Solution {
  public long maxAlternatingSum(int[] nums) {
    long even = 0; // the maximum alternating sum ending in an even index
    long odd = 0;  // the maximum alternating sum ending in an odd index

    for (final int num : nums) {
      even = Math.max(even, odd + num);
      odd = even - num;
    }

    return even;
  }
}
// code provided by PROGIEZ

1911. Maximum Alternating Subsequence Sum LeetCode Solution in Python

class Solution:
  def maxAlternatingSum(self, nums: list[int]) -> int:
    even = 0  # the maximum alternating sum ending in an even index
    odd = 0  # the maximum alternating sum ending in an odd index

    for num in nums:
      even = max(even, odd + num)
      odd = even - num

    return even
 # code by PROGIEZ