Watch 10 video solutions for Maximize Total Cost of Alternating Subarrays, a medium level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 4,456 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem Overview: You are given an integer array and can split it into multiple subarrays. The cost of a subarray is calculated using an alternating sum pattern like a[l] - a[l+1] + a[l+2] - .... Your goal is to choose split points so the total cost of all subarrays is maximized.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
This problem naturally fits dynamic programming. As you iterate through the array, track two states: the best total when the current element contributes with a positive sign and when it contributes with a negative sign. When starting a new subarray, the element must appear with a positive sign. When extending an existing subarray, the sign alternates from the previous element. For each number x, update the states using transitions like extending (prev_negative + x) or starting fresh (x). This keeps the optimal total at every step while scanning the array once.
The key insight is that splitting the array resets the alternating pattern. That means every index has two choices: continue the current subarray (flip sign) or start a new one (positive sign again). Maintaining these two DP states captures both possibilities without explicitly testing every split combination.
Approach 2: Greedy State Optimization (O(n) time, O(1) space)
You can implement the same idea using a greedy-style rolling update while iterating through the array. Instead of storing a full DP table, keep two running values: addState (current element treated as +) and subState (current element treated as -). For each new element, compute the best way to reach those states using previous values. Starting a new subarray always maps to the positive state, while extending a previous one flips the sign.
This works because the optimal decision at index i depends only on the best states at i-1. No future information is required. The algorithm processes the array once, updates two variables per step, and keeps the running maximum total cost. Time complexity is O(n) with constant O(1) space, making it efficient even for large inputs.
Recommended for interviews: The dynamic programming formulation is the clearest explanation during interviews. It shows you understand state transitions and optimal substructure. After presenting the DP idea, compress it into the greedy-style two-variable implementation to demonstrate optimization skills. Interviewers typically expect the final O(n) time and O(1) space solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (State Tracking) | O(n) | O(1) | Best for explaining the problem clearly in interviews and understanding alternating state transitions. |
| Greedy State Optimization | O(n) | O(1) | Preferred production solution. Minimal memory usage with a single pass through the array. |