D
DevExCode

LeetCode 1911: Maximum Alternating Subsequence Sum Solution

Master LeetCode problem 1911 (Maximum Alternating Subsequence Sum), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1911. Maximum Alternating Subsequence Sum

Medium
ArrayDynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming to keep track of the maximum alternating sum ending at each index of the array. At each index, we have two choices: either include the element in the current subsequence or exclude it. We need to consider both possibilities to find the maximum alternating sum.

We can define two values at each index i:

  • evenSum[i] as the maximum alternating sum ending at index i with the last element included at an even index.
  • oddSum[i] as the maximum alternating sum ending at index i with the last element included at an odd index.

The maximum alternating sum ending at index i can be calculated as the maximum of two cases:

  1. Include the element at index i:
    • If i is even, evenSum[i] = max(evenSum[i-1], oddSum[i-1] + nums[i]).
    • If i is odd, oddSum[i] = max(oddSum[i-1], evenSum[i-1] - nums[i]).
  2. Exclude the element at index i: evenSum[i] = max(evenSum[i-1], oddSum[i-1]) and oddSum[i] = max(oddSum[i-1], evenSum[i-1]).

Finally, the maximum alternating sum can be found by taking the maximum of evenSum[nums.length-1] and oddSum[nums.length-1].

Solution Code

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long evenSum = 0, oddSum = 0;
        for (int num : nums) {
            long newEven = Math.max(evenSum, oddSum + num);
            long newOdd = Math.max(oddSum, evenSum - num);
            evenSum = newEven;
            oddSum = newOdd;
        }
        return Math.max(evenSum, oddSum);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1911 (Maximum Alternating Subsequence Sum)?

This page provides optimized solutions for LeetCode problem 1911 (Maximum Alternating Subsequence Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1911 (Maximum Alternating Subsequence Sum)?

The time complexity for LeetCode 1911 (Maximum Alternating Subsequence Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1911 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1911 in Java, C++, or Python.

Back to LeetCode Solutions