# Maximize Total Cost of Alternating Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-total-cost-of-alternating-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/maximize-total-cost-of-alternating-subarrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` with length `n`.

The **cost** of a subarray `nums[l..r]`, where `0 <= l <= r < n`, is defined as:

`cost(l, r) = nums[l] - nums[l + 1] + ... + nums[r] * (−1)r − l`

Your task is to **split** `nums` into subarrays such that the **total** **cost** of the subarrays is **maximized**, ensuring each element belongs to **exactly one** subarray.

Formally, if `nums` is split into `k` subarrays, where `k > 1`, at indices `i1, i2, ..., ik − 1`, where `0 <= i1 < i2 < ... < ik - 1 < n - 1`, then the total cost will be:

`cost(0, i1) + cost(i1 + 1, i2) + ... + cost(ik − 1 + 1, n − 1)`

Return an integer denoting the _maximum total cost_ of the subarrays after splitting the array optimally.

**Note:** If `nums` is not split into subarrays, i.e. `k = 1`, the total cost is simply `cost(0, n - 1)`.

**Example 1:**

**Input:** nums = \[1,-2,3,4\]

**Output:** 10

**Explanation:**

One way to maximize the total cost is by splitting `[1, -2, 3, 4]` into subarrays `[1, -2, 3]` and `[4]`. The total cost will be `(1 + 2 + 3) + 4 = 10`.

**Example 2:**

**Input:** nums = \[1,-1,1,-1\]

**Output:** 4

**Explanation:**

One way to maximize the total cost is by splitting `[1, -1, 1, -1]` into subarrays `[1, -1]` and `[1, -1]`. The total cost will be `(1 + 1) + (1 + 1) = 4`.

**Example 3:**

**Input:** nums = \[0\]

**Output:** 0

**Explanation:**

We cannot split the array further, so the answer is 0.

**Example 4:**

**Input:** nums = \[1,-1\]

**Output:** 2

**Explanation:**

Selecting the whole array gives a total cost of `1 + 1 = 2`, which is the maximum.

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Recursive Approach with Memoization
A natural way to approach this problem is to think about the choices we can make at each step. When we are at an index `i`, we need to decide where the current subarray, starting at `i`, will end. Let's say it ends at index `j`. We would then calculate the cost of this subarray `nums[i...j]` and recursively solve the problem for the remaining part of the array, `nums[j+1...]`. This forms a recursive structure.

This plain recursive approach would be very slow due to re-computing solutions for the same subproblems. We can significantly improve it by using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This turns the exponential complexity into a polynomial one.
**Time:** O(N^2). There are `N` states (`i` from 0 to `n-1`). For each state `solve(i)`, we loop from `j = i` to `n-1`, which takes `O(N-i)` time. The total time complexity is the sum of `(N-i)` for `i` from 0 to `N-1`, which is `O(N^2)`. · **Space:** O(N) for the recursion stack depth in the worst case and for the memoization array.
**Pros:** It's a direct translation of the problem's recursive nature.; It's conceptually easier to formulate than more optimized solutions.
**Cons:** The `O(N^2)` time complexity is too slow for the given constraints (`n <= 10^5`) and will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
We define a function `solve(i)` that returns the maximum total cost we can obtain from the subarray `nums[i...n-1]`. The final answer to the problem will be `solve(0)`.

To compute `solve(i)`, we consider all possible split points. The first subarray must start at `i`. Let's say it ends at `j`, where `i <= j < n`. The cost for this split is `cost(i, j) + solve(j+1)`. We need to find the `j` that maximizes this value.

The `cost(i, j)` is calculated as `nums[i] - nums[i+1] + ... + (-1)^(j-i) * nums[j]`. We can compute this cost inside the loop that iterates over `j`.

To avoid recomputing `solve(k)` for the same `k` multiple times, we use a memoization table (e.g., a `long[] memo`) to store the results. The state of our DP is just the starting index `i`, so we need a 1D array for memoization.

```java
class Solution {
    private long[] memo;
    private int[] nums;
    private int n;

    public long maximumTotalCost(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.memo = new long[n];
        Arrays.fill(memo, Long.MIN_VALUE);
        return solve(0);
    }

    private long solve(int i) {
        if (i >= n) {
            return 0;
        }
        if (memo[i] != Long.MIN_VALUE) {
            return memo[i];
        }

        long maxCost = Long.MIN_VALUE;
        long currentSubarrayCost = 0;
        for (int j = i; j < n; j++) {
            if ((j - i) % 2 == 0) {
                currentSubarrayCost += nums[j];
            } else {
                currentSubarrayCost -= nums[j];
            }
            maxCost = Math.max(maxCost, currentSubarrayCost + solve(j + 1));
        }

        return memo[i] = maxCost;
    }
}
```
### Algorithm
- Define a recursive function, say `solve(i)`, that computes the maximum possible cost for the suffix of the array starting at index `i`, i.e., `nums[i:]`.
- The base case for the recursion is when `i` reaches the end of the array (`i >= n`), in which case the cost is 0.
- For a given `i`, we can form the first subarray in multiple ways. It can be `nums[i:i]`, `nums[i:i+1]`, ..., `nums[i:n-1]`. 
- If we choose the first subarray to be `nums[i:j]`, the total cost will be `cost(i, j)` plus the maximum cost for the rest of the array, which is `solve(j+1)`.
- We iterate through all possible end points `j` from `i` to `n-1`, calculate the total cost for each choice, and take the maximum.
- `solve(i) = max_{i <= j < n} (cost(i, j) + solve(j+1))`
- This recursive solution has overlapping subproblems (e.g., `solve(k)` is computed multiple times). We can optimize this by using memoization. We use an array, say `memo`, to store the results of `solve(i)` once computed.
- Before computing `solve(i)`, we check if the result is already in `memo`. If so, we return it directly.

## Linear Time Dynamic Programming
The `O(N^2)` solution can be improved by re-framing the decision at each step. Instead of deciding where a subarray ends, let's consider each element `nums[i]` and decide its role. For any element `nums[i]`, it can either start a new subarray or continue the one ending at `nums[i-1]`. The sign of `nums[i]`'s contribution depends on its position within its subarray.

This leads to a linear time dynamic programming solution. The state of our DP at index `i` needs to capture two possibilities: the maximum cost ending with `nums[i]` being added, and the maximum cost ending with `nums[i]` being subtracted. This is because the choice for `nums[i+1]` will depend on whether `nums[i]` was added or subtracted.
**Time:** O(N) because we iterate through the input array once, performing constant time operations at each step. · **Space:** O(N) to store the 2D DP table of size `n x 2`.
**Pros:** Highly efficient with O(N) time complexity, which passes the given constraints.; It's a systematic way to solve the problem by building up the solution.
**Cons:** Uses O(N) extra space, which can be optimized away since each state only depends on the previous one.
### Explanation
Let `dp[i][0]` be the maximum cost for a split of `nums[0...i]` where `nums[i]` has a positive sign, and `dp[i][1]` be the maximum cost where `nums[i]` has a negative sign.

For `nums[i]` to have a positive sign, it can either be the start of a new subarray (position 0, which is even) or be at an even distance from the start of its current subarray. If it starts a new subarray, the total cost is the maximum cost from the prefix `nums[0...i-1]` plus `nums[i]`. If it continues a subarray, it must follow an element with a negative sign. The recurrence relation captures both cases optimally.

For `nums[i]` to have a negative sign, it must continue a subarray and follow an element that had a positive sign.

This logic gives us the recurrence relations to build up the solution from `i=0` to `n-1`.

```java
class Solution {
    public long maximumTotalCost(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        long[][] dp = new long[n][2];

        // Base case: i = 0
        // dp[i][0]: max cost ending at i with nums[i] added
        // dp[i][1]: max cost ending at i with nums[i] subtracted
        dp[0][0] = nums[0];
        dp[0][1] = Long.MIN_VALUE; // Cannot subtract the first element

        for (int i = 1; i < n; i++) {
            // To add nums[i], we can either start a new subarray or continue one
            // where the previous element was subtracted.
            // Start new: max(dp[i-1][0], dp[i-1][1]) + nums[i]
            // Continue: dp[i-1][1] + nums[i]
            // The max of these is max(dp[i-1][0], dp[i-1][1]) + nums[i]
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + nums[i];

            // To subtract nums[i], we must continue a subarray where the
            // previous element was added.
            dp[i][1] = dp[i-1][0] - nums[i];
        }

        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}
```
### Algorithm
- We define a 2D DP array, `dp[n][2]`, where `n` is the length of `nums`.
- `dp[i][0]` will store the maximum total cost for the prefix `nums[0...i]`, assuming `nums[i]` contributes positively to the cost (i.e., it's at an even-indexed position within its subarray).
- `dp[i][1]` will store the maximum total cost for the prefix `nums[0...i]`, assuming `nums[i]` contributes negatively.
- **Base Case (i=0):** `nums[0]` must start a new subarray, so it's always added. 
  - `dp[0][0] = nums[0]`
  - `dp[0][1]` is impossible, so we initialize it to a very small number (negative infinity).
- **Transitions (for i > 0):**
  - To compute `dp[i][0]` (`nums[i]` is added): This can happen in two ways: 
    1. Start a new subarray at `i`. The cost is `max(dp[i-1][0], dp[i-1][1]) + nums[i]`.
    2. Continue the previous subarray. `nums[i]` is added if `nums[i-1]` was subtracted. The cost is `dp[i-1][1] + nums[i]`.
    The recurrence is `dp[i][0] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][1]) + nums[i]`, which simplifies to `dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + nums[i]`.
  - To compute `dp[i][1]` (`nums[i]` is subtracted): This can only happen by continuing a subarray where `nums[i-1]` was added. The cost is `dp[i-1][0] - nums[i]`.
- **Final Answer:** After iterating through the whole array, the maximum possible cost is `max(dp[n-1][0], dp[n-1][1])`.

## Space-Optimized Linear DP
The linear time DP approach is efficient, but we can observe that the computation for `dp[i]` only depends on the values from `dp[i-1]`. This means we don't need to store the entire `dp` table of size `n x 2`. We only need to keep track of the two state values from the previous step, `dp[i-1][0]` and `dp[i-1][1]`. This allows us to optimize the space complexity from `O(N)` down to `O(1)`.
**Time:** O(N), as it involves a single pass through the array. · **Space:** O(1), as we only use a constant number of variables to store the DP states regardless of the input size.
**Pros:** Optimal solution with O(N) time and O(1) space complexity.; Very efficient for large inputs.
**Cons:** The logic can be slightly less intuitive to grasp initially compared to the version with the full DP table.
### Explanation
We can get rid of the `dp` array and use just two variables to maintain the state. Let's call them `add` and `sub`.

- `add`: Represents `dp[i-1][0]`, the max cost of a prefix ending at `i-1` where `nums[i-1]` was added.
- `sub`: Represents `dp[i-1][1]`, the max cost of a prefix ending at `i-1` where `nums[i-1]` was subtracted.

We iterate through the array, and at each index `i`, we calculate the new values for `add` and `sub` based on their previous values and `nums[i]`. Since the new `sub` depends on the old `add`, we need to be careful with the order of updates or use a temporary variable.

```java
class Solution {
    public long maximumTotalCost(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        // add: max cost ending at previous element, with it being added
        // sub: max cost ending at previous element, with it being subtracted
        long add = nums[0];
        long sub = Long.MIN_VALUE; // Cannot subtract the first element

        for (int i = 1; i < n; i++) {
            long prev_add = add;
            
            // Calculate new 'add' for current index i
            // This is max(previous add, previous sub) + nums[i]
            add = Math.max(add, sub) + nums[i];
            
            // Calculate new 'sub' for current index i
            // This is previous add - nums[i]
            sub = prev_add - nums[i];
        }

        return Math.max(add, sub);
    }
}
```
### Algorithm
- Initialize two variables, `add` and `sub`, to represent the maximum cost for the prefix ending at the previous element (`i-1`), where `nums[i-1]` was added and subtracted, respectively.
- For the first element `nums[0]`, initialize `add = nums[0]` and `sub` to a very small number (as it cannot be subtracted).
- Iterate from `i = 1` to `n-1`:
  - At each step `i`, we want to compute the new `add` and `sub` values for the prefix ending at `i`.
  - Let `prev_add = add` and `prev_sub = sub` from the previous step.
  - The new `add` value (`current_add`) is `max(prev_add, prev_sub) + nums[i]`.
  - The new `sub` value (`current_sub`) is `prev_add - nums[i]`.
  - Update `add = current_add` and `sub = current_sub` for the next iteration. Note that the update for `sub` must use the `add` value from the *previous* step, so a temporary variable is needed.
- After the loop finishes, the maximum total cost for the entire array is `max(add, sub)`.

# Solutions
### Java

```java
class Solution {
private
  Long[][] f;
private
  int[] nums;
private
  int n;
public
  long maximumTotalCost(int[] nums) {
    n = nums.length;
    this.nums = nums;
    f = new Long[n][2];
    return dfs(0, 0);
  }
private
  long dfs(int i, int j) {
    if (i >= n) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    f[i][j] = nums[i] + dfs(i + 1, 1);
    if (j == 1) {
      f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));
    }
    return f[i][j];
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumTotalCost(vector<int> &nums) {
    int n = nums.size();
    long long f[n][2];
    fill(f[0], f[n], LLONG_MIN);
    auto dfs = [&](auto &&dfs, int i, int j) -> long long {
      if (i >= n) {
        return 0;
      }
      if (f[i][j] != LLONG_MIN) {
        return f[i][j];
      }
      f[i][j] = nums[i] + dfs(dfs, i + 1, 1);
      if (j) {
        f[i][j] = max(f[i][j], -nums[i] + dfs(dfs, i + 1, 0));
      }
      return f[i][j];
    };
    return dfs(dfs, 0, 0);
  }
};

```

### Python

```python
class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if i >= len(nums): return 0 ans = nums[i] + dfs(i + 1, 1) if j == 1: ans = max(ans, - nums[i] + dfs(i + 1, 0)) return ans return dfs(0, 0)

```