Skip to content

3196. Maximize Total Cost of Alternating Subarrays

Description

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

Solutions

Solution 1: 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 $\textit{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 $\textit{dfs}(0, 0)$.

The execution process of the function $dfs(i, j)$ is as follows:

  • If $i \geq \textit{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] + \textit{dfs}(i + 1, 1)$; if $j = 1$, it means the $i$-th number can be flipped, in which case the answer is $\max(\textit{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$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(nums):
                return 0
            ans = nums[i] + dfs(i + 1, 1)
            if j == 1:
                ans = max(ans, -nums[i] + dfs(i + 1, 0))
            return ans

        return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private Long[][] f;
    private int[] nums;
    private int n;

    public long maximumTotalCost(int[] nums) {
        n = nums.length;
        this.nums = nums;
        f = new Long[n][2];
        return dfs(0, 0);
    }

    private long dfs(int i, int j) {
        if (i >= n) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        f[i][j] = nums[i] + dfs(i + 1, 1);
        if (j == 1) {
            f[i][j] = Math.max(f[i][j], -nums[i] + dfs(i + 1, 0));
        }
        return f[i][j];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    long long maximumTotalCost(vector<int>& nums) {
        int n = nums.size();
        long long f[n][2];
        fill(f[0], f[n], LLONG_MIN);
        auto dfs = [&](auto&& dfs, int i, int j) -> long long {
            if (i >= n) {
                return 0;
            }
            if (f[i][j] != LLONG_MIN) {
                return f[i][j];
            }
            f[i][j] = nums[i] + dfs(dfs, i + 1, 1);
            if (j) {
                f[i][j] = max(f[i][j], -nums[i] + dfs(dfs, i + 1, 0));
            }
            return f[i][j];
        };
        return dfs(dfs, 0, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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);
}

Solution 2: 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)$.

1
2
3
4
5
6
class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        f, g = -inf, 0
        for x in nums:
            f, g = max(f, g) + x, f - x
        return max(f, g)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public long maximumTotalCost(int[] nums) {
        long f = Long.MIN_VALUE / 2, g = 0;
        for (int x : nums) {
            long ff = Math.max(f, g) + x;
            long gg = f - x;
            f = ff;
            g = gg;
        }
        return Math.max(f, g);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    long long maximumTotalCost(vector<int>& nums) {
        long long f = LLONG_MIN / 2, g = 0;
        for (int x : nums) {
            long long ff = max(f, g) + x, gg = f - x;
            f = ff;
            g = gg;
        }
        return max(f, g);
    }
};

1
2
3
4
5
6
7
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))
}

1
2
3
4
5
6
7
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);
}

Comments