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.
The greedy approach focuses on maximizing the positive differences between pairs of elements as we traverse the array. The problem shares similar traits with the "maximum subarray sum" problem but emphasizes on alternating costs.
For each element, decide whether to continue the existing subarray or start a new one based on whether extending the subarray yields a positive cost increment.
We initialize the currentCost with the first element and iterate the array. For each step, calculate the difference and based on the parity decide to negate if required. Add this to currentCost if it results in a greater value than starting a new subarray, else finalize the currentCost to totalCost and start a new subarray.
Time Complexity: O(n), where n is the length of the input array. Each element is visited once.
Space Complexity: O(1), no extra space required except for storing variables.
Use a dynamic programming strategy where each position records the best cost obtainable either including the last element in the current subarray or starting a new subarray. This method accumulates optimal decisions leading to a global optimum.
The DP array, dp, stores maximum cost ending at each position. Build the solution by choosing the best option at each step: extend the current subarray or take the new element with adjusted difference.
Time Complexity: O(n)
Space Complexity: O(n) due to DP array.
Based on the problem description, if the current number has not been flipped, then the next one can either be flipped or not flipped; if the current number has been flipped, then the next one can only remain unflipped.
Therefore, we define a function dfs(i, j), which represents starting from the i-th number, whether the i-th number can be flipped, where j indicates whether the i-th number is flipped. If j = 0, it means the i-th number cannot be flipped, otherwise, it can be flipped. The answer is dfs(0, 0).
The execution process of the function dfs(i, j) is as follows:
i geq len(nums), it means the array has been fully traversed, return 0;i-th number can remain unflipped, in which case the answer is nums[i] + dfs(i + 1, 1); if j = 1, it means the i-th number can be flipped, in which case the answer is max(dfs(i + 1, 0) - nums[i]). We take the maximum of the two.To avoid repeated calculations, we can use memoization to save the results that have already been computed.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
We can transform the memoization search from Solution 1 into dynamic programming.
Define f and g as two states, where f represents the maximum value when the current number is not flipped, and g represents the maximum value when the current number is flipped.
Traverse the array nums, for the i-th number, we can update the values of f and g based on their states:
f is max(f, g) + x, indicating that if the current number is not flipped, the previous number can be flipped or not flipped;g is f - x, indicating that if the current number is flipped, the previous number cannot be flipped.The final answer is max(f, g).
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the input array. Each element is visited once. |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Memoization | — |
| Dynamic Programming | — |
| 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. |
3196. Maximize Total Cost of Alternating Subarrays | DP | 0/1 Knapsack • Aryan Mittal • 4,456 views views
Watch 9 more video solutions →Practice Maximize Total Cost of Alternating Subarrays with our built-in code editor and test cases.
Practice on FleetCode