# Maximum Alternating Subsequence Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-alternating-subsequence-sum)
Canonical: https://scaleengineer.com/dsa/problems/maximum-alternating-subsequence-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Quadratic Dynamic Programming
This approach uses dynamic programming with a straightforward state definition. We build two arrays, `dp_even` and `dp_odd`, to keep track of the maximum alternating sum for subsequences ending at each index `i`. `dp_even[i]` stores the maximum sum where `nums[i]` is at an even position (added), and `dp_odd[i]` is for when `nums[i]` is at an odd position (subtracted). To compute the value for index `i`, we must iterate through all previous indices `j < i` to find the optimal subsequence to extend. This leads to a nested loop structure and a quadratic time complexity.
**Time:** O(N^2), where N is the number of elements in `nums`. For each element, we iterate through all previous elements to find the maximums, leading to a nested loop. · **Space:** O(N), where N is the number of elements in `nums`. We use two arrays of size N to store the DP states.
**Pros:** It's a valid DP approach that correctly solves the problem.; It's more efficient than a brute-force exponential solution.
**Cons:** The O(N^2) time complexity is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
In this method, we define our DP states based on the last element of the subsequence.

Let `dp_even[i]` be the maximum alternating sum of a subsequence ending with `nums[i]`, where `nums[i]` is at an even position (0-indexed) in the subsequence.
Let `dp_odd[i]` be the maximum alternating sum of a subsequence ending with `nums[i]`, where `nums[i]` is at an odd position in the subsequence.

For each element `nums[i]`, we calculate `dp_even[i]` and `dp_odd[i]`:
- To get `dp_even[i]`, `nums[i]` is added. It can either be the first element of a new subsequence (sum `nums[i]`) or be appended to an existing subsequence that had an even number of elements. To maximize the sum, we find the maximum `dp_odd[j]` for all `j < i` and add `nums[i]` to it. So, `dp_even[i] = nums[i] + max(0, max_{j<i} dp_odd[j])`.
- To get `dp_odd[i]`, `nums[i]` is subtracted. It must be appended to an existing subsequence that had an odd number of elements. We find the maximum `dp_even[j]` for all `j < i` and subtract `nums[i]` from it. So, `dp_odd[i] = -nums[i] + max_{j<i} dp_even[j]`.

After filling the DP arrays, the answer is the maximum value across the entire `dp_even` array. The nested loops required to find the maximum of previous states make this an O(N^2) solution.

```java
public long maxAlternatingSum(int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    long[] dp_even = new long[n];
    long[] dp_odd = new long[n];
    long max_sum = 0;

    for (int i = 0; i < n; i++) {
        long max_prev_odd = 0;
        for (int j = 0; j < i; j++) {
            max_prev_odd = Math.max(max_prev_odd, dp_odd[j]);
        }
        dp_even[i] = (long)nums[i] + max_prev_odd;

        long max_prev_even = 0;
        for (int j = 0; j < i; j++) {
            max_prev_even = Math.max(max_prev_even, dp_even[j]);
        }
        // An odd-positioned element must follow an even-positioned one.
        if (max_prev_even > 0) {
            dp_odd[i] = max_prev_even - nums[i];
        } else {
            // Cannot form a valid subsequence of length > 1 ending at i in an odd position
            dp_odd[i] = Long.MIN_VALUE;
        }
        max_sum = Math.max(max_sum, dp_even[i]);
    }

    return max_sum;
}
```
### Algorithm
- Initialize two DP arrays, `dp_even` and `dp_odd`, of size `n`.
- `dp_even[i]` will store the maximum alternating sum of a subsequence from `nums[0...i]` that ends with `nums[i]` at an even-indexed position.
- `dp_odd[i]` will store the maximum alternating sum of a subsequence from `nums[0...i]` that ends with `nums[i]` at an odd-indexed position.
- Iterate through the `nums` array from `i = 0` to `n-1`:
  - To calculate `dp_even[i]`, `nums[i]` can either start a new subsequence (sum `nums[i]`) or be appended to a subsequence that ended at `j < i` at an odd position. We take the maximum over all possible `j`. The recurrence is: `dp_even[i] = nums[i] + max(0, max_{j<i} dp_odd[j])`.
  - To calculate `dp_odd[i]`, `nums[i]` must be appended to a subsequence that ended at `j < i` at an even position. The recurrence is: `dp_odd[i] = -nums[i] + max_{j<i} dp_even[j]`.
- The final answer is the maximum value in the `dp_even` array, as any optimal subsequence must have an odd length (since all numbers are positive).

## Linear Dynamic Programming with Auxiliary Arrays
This approach improves upon the O(N^2) DP solution by refining the state definition. Instead of tracking subsequences that *end* at index `i`, we track the best possible subsequence sum using elements *up to* index `i`. This change allows us to formulate a recurrence relation that only depends on the results from the immediately preceding index, `i-1`. This eliminates the need for the inner loop and reduces the time complexity to linear, O(N).
**Time:** O(N), as we perform a single pass through the input array. · **Space:** O(N), for the two DP arrays `even` and `odd`.
**Pros:** Achieves a linear time complexity, which is very efficient.; The logic is a direct and clear representation of the choices at each step.
**Cons:** While efficient in time, it uses O(N) extra space, which is not optimal for this problem.
### Explanation
We can optimize the DP by changing the state definition. Let `even[i]` be the maximum alternating sum of a subsequence from `nums[0...i]` having an odd length, and `odd[i]` be the maximum for a subsequence with an even length.

When considering `nums[i]`, we have two choices:
1.  **Don't include `nums[i]`**: The maximum sums remain the same as at `i-1`. So, `even[i-1]` and `odd[i-1]` are candidates.
2.  **Include `nums[i]`**: 
    - To form a new odd-length subsequence, we must add `nums[i]`. This means it's appended to a previous even-length subsequence. The best we can do is `odd[i-1] + nums[i]`.
    - To form a new even-length subsequence, we must subtract `nums[i]`. This means it's appended to a previous odd-length subsequence. The best we can do is `even[i-1] - nums[i]`.

Combining these choices gives the recurrence relations:
- `even[i] = max(even[i-1], odd[i-1] + nums[i])`
- `odd[i] = max(odd[i-1], even[i-1] - nums[i])`

The base case is `even[0] = nums[0]` (subsequence `[nums[0]]`) and `odd[0] = 0` (empty subsequence). The final answer is `even[n-1]`, as the maximum sum will always come from an odd-length subsequence.

```java
public long maxAlternatingSum(int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    long[] even = new long[n];
    long[] odd = new long[n];

    even[0] = nums[0];
    // odd[0] is implicitly 0, representing an empty subsequence

    for (int i = 1; i < n; i++) {
        even[i] = Math.max(even[i - 1], odd[i - 1] + nums[i]);
        odd[i] = Math.max(odd[i - 1], even[i - 1] - nums[i]);
    }

    return even[n - 1];
}
```
### Algorithm
- Define two DP arrays, `even` and `odd`, of size `n`.
- `even[i]` will store the maximum alternating sum of any subsequence from `nums[0...i]` that has an odd number of elements.
- `odd[i]` will store the maximum alternating sum of any subsequence from `nums[0...i]` that has an even number of elements.
- Initialize base cases: `even[0] = nums[0]` and `odd[0] = 0`.
- Iterate from `i = 1` to `n-1`:
  - `even[i] = max(even[i-1], odd[i-1] + nums[i])`. This considers either not taking `nums[i]` or taking it at an even position.
  - `odd[i] = max(odd[i-1], even[i-1] - nums[i])`. This considers either not taking `nums[i]` or taking it at an odd position.
- The final answer is `even[n-1]`.

## Space-Optimized Linear Dynamic Programming
This is the most efficient solution. It refines the linear DP approach by observing that the calculations for the current state `i` only depend on the state at `i-1`. This means we don't need to store the entire history in DP arrays. We can use just two variables to keep track of the latest maximum alternating sums for odd-length and even-length subsequences. This reduces the space complexity to a constant O(1) while maintaining the linear time complexity.
**Time:** O(N), for a single pass over the input array. · **Space:** O(1), as we only use a constant number of variables regardless of the input size.
**Pros:** Optimal O(N) time complexity.; Optimal O(1) space complexity.; The implementation is simple and concise.
**Cons:** There are no significant cons to this approach as it is optimal in both time and space.
### Explanation
This approach is a space optimization of the linear time DP. Since `even[i]` and `odd[i]` only depend on `even[i-1]` and `odd[i-1]`, we can get rid of the arrays and use only two variables.

Let `even` be the maximum alternating sum for an odd-length subsequence found so far.
Let `odd` be the maximum alternating sum for an even-length subsequence found so far.

We initialize both `even` and `odd` to 0, representing the sum of an empty subsequence. Then, we iterate through each number `num` in `nums` and update our variables:

- The new maximum `even` sum is either the existing `even` sum (if we don't include `num`) or `odd + num` (if we include `num` at an even position).
- The new maximum `odd` sum is either the existing `odd` sum or `even - num`. Crucially, when calculating the new `odd`, we must use the `even` value from *before* it was updated in the current step.

This logic can be seen as finding peaks and valleys. `even` tracks the maximum profit ending with a sale (a peak), and `odd` tracks the state after a purchase (a valley). The final answer is the maximum `even` sum after processing all numbers.

```java
public long maxAlternatingSum(int[] nums) {
    long even = 0; // Represents the max sum for a subsequence of odd length
    long odd = 0;  // Represents the max sum for a subsequence of even length

    for (int num : nums) {
        // Store the previous 'even' state before it's updated
        long prev_even = even;

        // The new max 'even' sum is either the old 'even' sum (don't pick num),
        // or the old 'odd' sum + num (pick num at an even position).
        even = Math.max(even, odd + num);

        // The new max 'odd' sum is either the old 'odd' sum (don't pick num),
        // or the 'even' sum from the previous state - num (pick num at an odd position).
        odd = Math.max(odd, prev_even - num);
    }

    return even;
}
```
### Algorithm
- Initialize two variables: `even = 0` (for max sum of odd-length subsequences) and `odd = 0` (for max sum of even-length subsequences).
- Iterate through each number `num` in the `nums` array:
  - Store the current `even` value in a temporary variable, e.g., `prev_even`.
  - Update `even`: `even = max(even, odd + num)`. This decides whether to extend an even-length subsequence with `num` or stick with the best odd-length subsequence found so far.
  - Update `odd`: `odd = max(odd, prev_even - num)`. This decides whether to extend an odd-length subsequence (using its old value `prev_even`) or stick with the best even-length subsequence.
- After iterating through all numbers, return `even`.

# Solutions
### Java

```java
class Solution {
public
  long maxAlternatingSum(int[] nums) {
    int n = nums.length;
    long[] f = new long[n + 1];
    long[] g = new long[n + 1];
    for (int i = 1; i <= n; ++i) {
      f[i] = Math.max(g[i - 1] - nums[i - 1], f[i - 1]);
      g[i] = Math.max(f[i - 1] + nums[i - 1], g[i - 1]);
    }
    return Math.max(f[n], g[n]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxAlternatingSum(vector<int> &nums) {
    int n = nums.size();
    vector<long long> f(n + 1), g(n + 1);
    for (int i = 1; i <= n; ++i) {
      f[i] = max(g[i - 1] - nums[i - 1], f[i - 1]);
      g[i] = max(f[i - 1] + nums[i - 1], g[i - 1]);
    }
    return max(f[n], g[n]);
  }
};

```

### Python

```python
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int: n = len(nums) f = [0] * (n + 1) g = [0] * (n + 1) for i, x in enumerate(nums, 1): f[i] = max(g[i - 1] - x, f[i - 1]) g[i] = max(f[i - 1] + x, g[i - 1]) return max(f[n], g[n])

```