Maximize Total Cost of Alternating Subarrays

Med

#2839Time: 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.

Patterns

Dynamic Programming

Data structures

Array

Prompt

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 i₁, i₂, ..., i_{k − 1}, where 0 <= i₁ < i₂ < ... < i_{k - 1} < n - 1, then the total cost will be:

cost(0, i₁) + cost(i₁ + 1, i₂) + ... + cost(i_{k − 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    private long[] memo;3    private int[] nums;4    private int n;5 6    public long maximumTotalCost(int[] nums) {7        this.nums = nums;8        this.n = nums.length;9        this.memo = new long[n];10        Arrays.fill(memo, Long.MIN_VALUE);11        return solve(0);12    }13 14    private long solve(int i) {15        if (i >= n) {16            return 0;17        }18        if (memo[i] != Long.MIN_VALUE) {19            return memo[i];20        }21 22        long maxCost = Long.MIN_VALUE;23        long currentSubarrayCost = 0;24        for (int j = i; j < n; j++) {25            if ((j - i) % 2 == 0) {26                currentSubarrayCost += nums[j];27            } else {28                currentSubarrayCost -= nums[j];29            }30            maxCost = Math.max(maxCost, currentSubarrayCost + solve(j + 1));31        }32 33        return memo[i] = maxCost;34    }35}

Complexity

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.

Trade-offs

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.

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.

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]).

Walkthrough

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.

1class Solution {2    public long maximumTotalCost(int[] nums) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7 8        long[][] dp = new long[n][2];9 10        // Base case: i = 011        // dp[i][0]: max cost ending at i with nums[i] added12        // dp[i][1]: max cost ending at i with nums[i] subtracted13        dp[0][0] = nums[0];14        dp[0][1] = Long.MIN_VALUE; // Cannot subtract the first element15 16        for (int i = 1; i < n; i++) {17            // To add nums[i], we can either start a new subarray or continue one18            // where the previous element was subtracted.19            // Start new: max(dp[i-1][0], dp[i-1][1]) + nums[i]20            // Continue: dp[i-1][1] + nums[i]21            // The max of these is max(dp[i-1][0], dp[i-1][1]) + nums[i]22            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + nums[i];23 24            // To subtract nums[i], we must continue a subarray where the25            // previous element was added.26            dp[i][1] = dp[i-1][0] - nums[i];27        }28 29        return Math.max(dp[n - 1][0], dp[n - 1][1]);30    }31}

Complexity

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`.

Trade-offs

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.

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).

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).

Walkthrough

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.

1class Solution {2    public long maximumTotalCost(int[] nums) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7 8        // add: max cost ending at previous element, with it being added9        // sub: max cost ending at previous element, with it being subtracted10        long add = nums[0];11        long sub = Long.MIN_VALUE; // Cannot subtract the first element12 13        for (int i = 1; i < n; i++) {14            long prev_add = add;15            16            // Calculate new 'add' for current index i17            // This is max(previous add, previous sub) + nums[i]18            add = Math.max(add, sub) + nums[i];19            20            // Calculate new 'sub' for current index i21            // This is previous add - nums[i]22            sub = prev_add - nums[i];23        }24 25        return Math.max(add, sub);26    }27}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  Long[][] f;4private5  int[] nums;6private7  int n;8public9  long maximumTotalCost(int[] nums) {10    n = nums.length;11    this.nums = nums;12    f = new Long[n][2];13    return dfs(0, 0);14  }15private16  long dfs(int i, int j) {17    if (i >= n) {18      return 0;19    }20    if (f[i][j] != null) {21      return f[i][j];22    }23    f[i][j] = nums[i] + dfs(i + 1, 1);24    if (j == 1) {25      f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));26    }27    return f[i][j];28  }29}

1class Solution {2public:3  long long maximumTotalCost(vector<int> &nums) {4    int n = nums.size();5    long long f[n][2];6    fill(f[0], f[n], LLONG_MIN);7    auto dfs = [&](auto &&dfs, int i, int j) -> long long {8      if (i >= n) {9        return 0;10      }11      if (f[i][j] != LLONG_MIN) {12        return f[i][j];13      }14      f[i][j] = nums[i] + dfs(dfs, i + 1, 1);15      if (j) {16        f[i][j] = max(f[i][j], -nums[i] + dfs(dfs, i + 1, 0));17      }18      return f[i][j];19    };20    return dfs(dfs, 0, 0);21  }22};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  Long[][] f;4private5  int[] nums;6private7  int n;8public9  long maximumTotalCost(int[] nums) {10    n = nums.length;11    this.nums = nums;12    f = new Long[n][2];13    return dfs(0, 0);14  }15private16  long dfs(int i, int j) {17    if (i >= n) {18      return 0;19    }20    if (f[i][j] != null) {21      return f[i][j];22    }23    f[i][j] = nums[i] + dfs(i + 1, 1);24    if (j == 1) {25      f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));26    }27    return f[i][j];28  }29}

1class Solution {2public:3  long long maximumTotalCost(vector<int> &nums) {4    int n = nums.size();5    long long f[n][2];6    fill(f[0], f[n], LLONG_MIN);7    auto dfs = [&](auto &&dfs, int i, int j) -> long long {8      if (i >= n) {9        return 0;10      }11      if (f[i][j] != LLONG_MIN) {12        return f[i][j];13      }14      f[i][j] = nums[i] + dfs(dfs, i + 1, 1);15      if (j) {16        f[i][j] = max(f[i][j], -nums[i] + dfs(dfs, i + 1, 0));17      }18      return f[i][j];19    };20    return dfs(dfs, 0, 0);21  }22};

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.