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] <= 109The key observation in #3196 Maximize Total Cost of Alternating Subarrays is that the cost of a subarray alternates signs: a[l] - a[l+1] + a[l+2] - .... This alternating structure suggests using dynamic programming to track whether the current element contributes positively or negatively to the total cost.
Maintain two DP states while iterating through the array. One state represents the maximum total when the current element is added with a positive sign, and the other when it is added with a negative sign. At each index, you can either extend the previous alternating subarray (flipping the sign) or start a new subarray, which resets the pattern so the current element becomes positive.
By updating these states in a single pass and always keeping the best previous total, we efficiently compute the optimal answer. The approach runs in O(n) time and can be optimized to O(1) space by storing only the latest DP values.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with alternating states | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The problem can be solved using dynamic programming.
Since we can always start a new subarray, the problem is the same as selecting some elements in the array and flipping their signs to negative to maximize the sum. However, we cannot flip the signs of 2 consecutive elements, and the first element in the array cannot be negative.
Let <code>dp[i][0/1]</code> be the largest sum we can get for prefix <code>nums[0..i]</code>, where <code>dp[i][0]</code> is the maximum if the <code>i<sup>th</sup></code> element wasn't flipped, and <code>dp[i][1]</code> is the maximum if the <code>i<sup>th</sup></code> element was flipped.
Based on the restriction:<br /> <code>dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + nums[i]</code><br /> <code>dp[i][1] = dp[i - 1][0] - nums[i]</code>
The initial state is:<br /> <code>dp[1][0] = nums[0] + nums[1]</code><br /> <code>dp[1][1] = nums[0] - nums[1]</code><br /> and the answer is <code>max(dp[n - 1][0], dp[n - 1][1])</code>.
Can you optimize the space complexity?
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving alternating sums and dynamic programming patterns are common in technical interviews. While this exact problem may vary, the underlying idea of state-based DP transitions is frequently tested in FAANG-style interviews.
No complex data structure is required. A few variables representing dynamic programming states are enough, making the solution both memory-efficient and easy to implement.
The optimal approach uses dynamic programming to track alternating contributions. By maintaining states for when the current element is added positively or negatively, we can decide whether to extend an existing subarray or start a new one while scanning the array once.
Dynamic programming works well because the sign of each element depends on the previous element's state. Tracking positive and negative contribution states allows the algorithm to efficiently update the best total cost at each step.