Maximize Total Cost of Alternating Subarrays solution and explanation
Google
9 more videos on this problem
3196. Maximize Total Cost of Alternating Subarrays | DP | 0/1 KnapsackAryan Mittal · 21:04 · 4K views
3196 Maximize Total Cost of Alternating Subarrays || How to 🤔 in Interview || DP ✅ || Memo 🔥Ayush Rao · 10:59 · 1K views
100337. Maximize Total Cost of Alternating Subarrays Solution | Leetcode Weekly Contest 403 SolutionJUST CODE · 0:53 · 920 views
3196. Maximize Total Cost of Alternating Subarrays (Leetcode Medium)Programming Live with Larry · 19:30 · 635 views
Leetcode | Weekly Contest 403 | B | C | 3195 | 3196 | Dynamic Programming | Editorial | Solution.Pretest Passed · 18:17 · 428 views
【每日一题】LeetCode 3196. Maximize Total Cost of Alternating SubarraysHuifeng Guan · 9:51 · 252 views
Leetcode Maximize Total Cost of Alternating Subarrays HindiThinkCode · 10:18 · 190 views
Leetcode Weekly contest 403 | Maximize Total Cost of Alternating Subarrays | Explaintaion | First 3WiseCoder · 39:01 · 133 views
3196. Maximize Total Cost of Alternating Subarrays | RecursionTech Courses · 7:12 · 132 views
Leetcode 3196 Maximize Total Cost of Alternating SubarraysSandip Jana · 14:04 · 108 views
The 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
Approach overview
Problem 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 1: Greedy Approach
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.
def max_cost(nums):
total_cost, current_cost = 0, nums[0]
n = len(nums)
for i in range(1, n):
diff = nums[i] - nums[i - 1]
if i % 2 == 0:
diff = -diff
if current_cost + diff > nums[i]:
current_cost += diff
else:
total_cost += current_cost
current_cost = nums[i]
total_cost += current_cost
return total_cost
nums = [1, -2, 3, 4]
print(max_cost(nums))public class MaxCost {
public static int maxCost(int[] nums) {
int totalCost = 0;
int currentCost = nums[0];
for (int i = 1; i < nums.length; i++) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
if (currentCost + diff > nums[i])
currentCost += diff;
else {
totalCost += currentCost;
currentCost = nums[i];
}
}
totalCost += currentCost;
return totalCost;
}
public static void main(String[] args) {
int[] nums = {1, -2, 3, 4};
System.out.println(maxCost(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxCost(vector<int>& nums) {
int totalCost = 0;
int currentCost = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
if (currentCost + diff > nums[i])
currentCost += diff;
else {
totalCost += currentCost;
currentCost = nums[i];
}
}
totalCost += currentCost;
return totalCost;
}
int main() {
vector<int> nums = {1, -2, 3, 4};
cout << maxCost(nums) << endl;
return 0;
}function maxCost(nums) {
let totalCost = 0;
let currentCost = nums[0];
for (let i = 1; i < nums.length; i++) {
let diff = nums[i] - nums[i - 1];
if (i % 2 === 0) diff = -diff;
if (currentCost + diff > nums[i]) {
currentCost += diff;
} else {
totalCost += currentCost;
currentCost = nums[i];
}
}
totalCost += currentCost;
return totalCost;
}
const nums = [1, -2, 3, 4];
console.log(maxCost(nums));#include <stdio.h>
#include <stdlib.h>
int maxCost(int* nums, int n) {
int totalCost = 0;
int currentCost = nums[0];
for (int i = 1; i < n; ++i) {
int diff = nums[i] - nums[i - 1];
if ((i % 2) == 0) {
diff = -diff;
}
if (currentCost + diff > nums[i]) {
currentCost += diff;
} else {
totalCost += currentCost; // finalize current subarray
currentCost = nums[i];
}
}
totalCost += currentCost;
return totalCost;
}
int main() {
int nums[] = {1, -2, 3, 4};
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxCost(nums, n));
return 0;
}using System;
class MaxCost {
static int MaxCostFn(int[] nums) {
int totalCost = 0;
int currentCost = nums[0];
for (int i = 1; i < nums.Length; i++) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
if (currentCost + diff > nums[i])
currentCost += diff;
else {
totalCost += currentCost;
currentCost = nums[i];
}
}
totalCost += currentCost;
return totalCost;
}
static void Main() {
int[] nums = { 1, -2, 3, 4 };
Console.WriteLine(MaxCostFn(nums));
}
}The strategy involves adjusting the currentCost depending on parity. This dynamic handling aligns well with maximizing cost accumulation across dynamic splits.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Dynamic Programming Approach
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.
def max_cost(nums):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
diff = nums[i] - nums[i - 1]
if i % 2 == 0:
diff = -diff
dp[i] = max(nums[i], dp[i - 1] + diff)
return dp[-1]
nums = [1, -2, 3, 4]
print(max_cost(nums))public class MaxCost {
public static int maxCost(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
dp[i] = Math.max(nums[i], dp[i - 1] + diff);
}
return dp[n - 1];
}
public static void main(String[] args) {
int[] nums = {1, -2, 3, 4};
System.out.println(maxCost(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxCost(vector<int>& nums) {
vector<int> dp(nums.size());
dp[0] = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
dp[i] = nums[i] + max(dp[i - 1], diff);
}
return dp.back();
}
int main() {
vector<int> nums = {1, -2, 3, 4};
cout << maxCost(nums) << endl;
return 0;
}function maxCost(nums) {
const n = nums.length;
const dp = Array(n).fill(0);
dp[0] = nums[0];
for (let i = 1; i < n; i++) {
let diff = nums[i] - nums[i - 1];
if (i % 2 === 0) diff = -diff;
dp[i] = Math.max(nums[i], dp[i - 1] + diff);
}
return dp[n - 1];
}
const nums = [1, -2, 3, 4];
console.log(maxCost(nums));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int maxCost(int* nums, int n) {
int* dp = (int*)malloc(n * sizeof(int));
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
int diff = nums[i] - nums[i - 1];
if ((i % 2) == 0) {
diff = -diff;
}
dp[i] = nums[i] + fmax(dp[i - 1], diff);
}
int result = dp[n - 1];
free(dp);
return result;
}
int main() {
int nums[] = {1, -2, 3, 4};
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxCost(nums, n));
return 0;
}using System;
class MaxCost {
static int MaxCostFn(int[] nums) {
int n = nums.Length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
int diff = nums[i] - nums[i - 1];
if (i % 2 == 0) diff = -diff;
dp[i] = Math.Max(nums[i], dp[i - 1] + diff);
}
return dp[n - 1];
}
static void Main() {
int[] nums = { 1, -2, 3, 4 };
Console.WriteLine(MaxCostFn(nums));
}
}The Python DP solution elegantly channels the essence of maximal subsequences, maintaining an optimal sum as the array is processed incrementally.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Memoization
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:
- If
i geq len(nums), it means the array has been fully traversed, return0; - Otherwise, the
i-th number can remain unflipped, in which case the answer isnums[i] + dfs(i + 1, 1); ifj = 1, it means thei-th number can be flipped, in which case the answer ismax(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.
function maximumTotalCost(nums: number[]): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-Infinity));
const dfs = (i: number, j: number): number => {
if (i >= n) {
return 0;
}
if (f[i][j] !== -Infinity) {
return f[i][j];
}
f[i][j] = nums[i] + dfs(i + 1, 1);
if (j) {
f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));
}
return f[i][j];
};
return dfs(0, 0);
}func maximumTotalCost(nums []int) int64 {
n := len(nums)
f := make([][2]int64, n)
for i := range f {
f[i] = [2]int64{-1e18, -1e18}
}
var dfs func(int, int) int64
dfs = func(i, j int) int64 {
if i >= n {
return 0
}
if f[i][j] != -1e18 {
return f[i][j]
}
f[i][j] = int64(nums[i]) + dfs(i+1, 1)
if j > 0 {
f[i][j] = max(f[i][j], int64(-nums[i])+dfs(i+1, 0))
}
return f[i][j]
}
return dfs(0, 0)
}Approach 4: Dynamic Programming
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:
- If the current number is not flipped, then the value of
fismax(f, g) + x, indicating that if the current number is not flipped, the previous number can be flipped or not flipped; - If the current number is flipped, then the value of
gisf - 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).
function maximumTotalCost(nums: number[]): number {
let [f, g] = [-Infinity, 0];
for (const x of nums) {
[f, g] = [Math.max(f, g) + x, f - x];
}
return Math.max(f, g);
}func maximumTotalCost(nums []int) int64 {
f, g := math.MinInt64/2, 0
for _, x := range nums {
f, g = max(f, g)+x, f-x
}
return int64(max(f, g))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) |
| Dynamic Programming Approach | Time Complexity: O(n). |
| Memoization | – |
| Dynamic Programming | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximize Total Cost of Alternating Subarrays easy or hard?
Maximize Total Cost of Alternating Subarrays is rated Medium difficulty. The challenge is identifying the correct dynamic programming states and realizing that splitting the array resets the alternating sign pattern. Once the two-state transition is understood, the implementation becomes straightforward.
Maximize Total Cost of Alternating Subarrays Python/Java solution
Python, Java, C++, and other implementations follow the same idea: maintain two variables for positive and negative alternating states and update them while scanning the array. Each iteration computes the best extension or restart option. The final answer is the maximum positive-state value after processing all elements.
How to solve Maximize Total Cost of Alternating Subarrays in O(n)?
Iterate through the array while maintaining two values: the best total if the current element is added with a positive sign and the best total if it is subtracted. Update these values using the previous states to represent extending or restarting a subarray. This dynamic programming transition ensures the maximum total cost is tracked in a single pass.
What is the best approach for Maximize Total Cost of Alternating Subarrays?
The best approach uses dynamic programming with two states representing whether the current element contributes positively or negatively to the alternating sum. At each index you either extend the current subarray (flip the sign) or start a new subarray (positive sign). This runs in O(n) time and O(1) space by maintaining only two running values.
Is Maximize Total Cost of Alternating Subarrays asked at Google/Amazon/Meta?
Alternating sum and dynamic programming partition problems are common in interviews at companies like Google, Amazon, and Meta. Variations often test state transitions, greedy optimization, or maximum subarray style reasoning, making this problem a useful interview practice question.
What data structure is used in Maximize Total Cost of Alternating Subarrays?
The solution mainly uses simple variables while iterating through the array. Conceptually it relies on dynamic programming states, but no additional data structures such as heaps or hash maps are required. The algorithm only tracks two running values representing alternating states.
What is the time complexity of Maximize Total Cost of Alternating Subarrays?
The optimal solution runs in O(n) time because the array is processed once while maintaining two DP states. Each step performs constant-time updates. Space complexity is O(1) since only two variables are needed instead of a full DP table.