Skip to main content
Talentd

Maximize Total Cost of Alternating Subarrays - Solution & Explanation

MediumArrayDynamic Programming24 min readAsked at: Google
Practice this problem

Problem Statement

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to DP array.

Try this approach in the editor →

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, return 0;
  • Otherwise, the 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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 f is max(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 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

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.

Dynamic Programming Approach

Time Complexity: O(n)
Space Complexity: O(n) due to DP array.

Memoization—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 OptimizationO(n)O(1)Preferred production solution. Minimal memory usage with a single pass through the array.

Video Solution

3196. Maximize Total Cost of Alternating Subarrays | DP | 0/1 Knapsack • Aryan Mittal • 4,491 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximize Total Cost of Alternating Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays