Maximize Total Cost of Alternating Subarrays

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).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19



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 <= 10^5
-109 <= nums[i] <= 10^9

Solution

Method 1 – Dynamic Programming with Alternating Sums

Intuition

The cost function alternates the sign for each element in a subarray, starting with positive. This is similar to maximizing the sum of subarrays where the sign alternates. We can use dynamic programming to keep track of the best possible sum ending at each index, considering the alternation.

Approach

For each index, maintain two states:
- The maximum total cost ending at this index with the last element being added (even index in subarray).
- The maximum total cost ending at this index with the last element being subtracted (odd index in subarray).
At each step, decide whether to start a new subarray or extend the previous one.
The answer is the maximum value among all possible ending states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    long long maximumCost(vector<int>& nums) {
        long long ans = LLONG_MIN, even = 0, odd = LLONG_MIN;
        for (int x : nums) {
            long long new_even = max(even + x, odd - x);
            long long new_odd = max(odd, even - x);
            even = new_even;
            odd = new_odd;
            ans = max(ans, even);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func maximumCost(nums []int) int64 {
    even, odd := int64(0), int64(-1<<63)
    ans := int64(-1<<63)
    for _, x := range nums {
        nx := int64(x)
        newEven := max(even+nx, odd-nx)
        newOdd := max(odd, even-nx)
        even, odd = newEven, newOdd
        ans = max(ans, even)
    }
    return ans
}
func max(a, b int64) int64 {
    if a > b { return a }
    return b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public long maximumCost(int[] nums) {
        long ans = Long.MIN_VALUE, even = 0, odd = Long.MIN_VALUE;
        for (int x : nums) {
            long newEven = Math.max(even + x, odd - x);
            long newOdd = Math.max(odd, even - x);
            even = newEven;
            odd = newOdd;
            ans = Math.max(ans, even);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    fun maximumCost(nums: IntArray): Long {
        var ans = Long.MIN_VALUE
        var even = 0L
        var odd = Long.MIN_VALUE
        for (x in nums) {
            val newEven = maxOf(even + x, odd - x)
            val newOdd = maxOf(odd, even - x)
            even = newEven
            odd = newOdd
            ans = maxOf(ans, even)
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def maximumCost(self, nums: list[int]) -> int:
        ans = float('-inf')
        even = 0
        odd = float('-inf')
        for x in nums:
            new_even = max(even + x, odd - x)
            new_odd = max(odd, even - x)
            even, odd = new_even, new_odd
            ans = max(ans, even)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
    pub fn maximum_cost(nums: Vec<i32>) -> i64 {
        let mut ans = i64::MIN;
        let mut even = 0i64;
        let mut odd = i64::MIN;
        for &x in &nums {
            let nx = x as i64;
            let new_even = even.max(odd - nx) + nx;
            let new_odd = odd.max(even - nx);
            even = new_even;
            odd = new_odd;
            ans = ans.max(even);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    maximumCost(nums: number[]): number {
        let ans = -Infinity, even = 0, odd = -Infinity;
        for (const x of nums) {
            const newEven = Math.max(even + x, odd - x);
            const newOdd = Math.max(odd, even - x);
            even = newEven;
            odd = newOdd;
            ans = Math.max(ans, even);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of nums, since we process each element once.
🧺 Space complexity: O(1), as we only use a constant number of variables.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Dynamic Programming with Alternating Sums#

Intuition#

Approach#

Code#

Complexity#