Skip to content

3196. Maximize Total Cost of Alternating Subarrays

SourceWeekly Contest 403 Q3DifficultyMediumRating1846

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

Thinking

A partition scores each piece with alternating signs and a positive first term. All partitions are exponential.

Whether the current value may be negated depends only on whether the previous one already was: a negation forces the next term positive.

Memoize \(\textit{dfs}(i,j)\) with \(j=1\) meaning a negation is allowed. Always try \(\textit{nums}[i]+\textit{dfs}(i+1,1)\), and if allowed also \(-\textit{nums}[i]+\textit{dfs}(i+1,0)\).

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 \(\textit{dfs}(i, j)\) is as follows:

  • If \(i \geq \textit{len}(\textit{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 \(\textit{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) - \textit{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 \(\textit{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 = [&](this 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(i + 1, 1);
            if (j) {
                f[i][j] = max(f[i][j], -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
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

Thinking

Method 1 fills a linear table from the end. The two choices roll into two scalars.

\(f\) is the best score if the current value stays positive, \(g\) if it is negated. A negation requires the previous value to have stayed positive.

Set \(f=\max(f,g)+x\) and \(g=f_{\textit{old}}-x\). The answer is \(\max(f,g)\) in constant extra space.

We can compress the table from Solution 1 into two rolling values.

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 \(\textit{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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).

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);
}

Solution 3: Dynamic Programming

Thinking

A partition scores each piece with alternating signs and a positive first term. All partitions are exponential, and \(n\le 10^5\).

Whether the current value may be negated depends only on the next suffix: a positive term continues with a negation allowed, and a negation forces the next term positive.

Searching that recurrence still calls the next index before it returns, so the chain has depth \(n\) and overflows the stack.

The next index is known if we walk from the end. Let \(f[i][j]\) be the best score from \(i\) when \(j=1\) allows negating \(\textit{nums}[i]\). Fill \(i\) from \(n-1\) down to \(0\) and return \(f[0][0]\).

If the current number stays positive, the next one may be negated or stay positive. If the current number is negated, the next one must stay positive.

Let \(f[i][j]\) be the best score of the suffix starting at index \(i\), where \(j = 1\) means \(\textit{nums}[i]\) may be negated and \(j = 0\) means it must stay positive. The answer is \(f[0][0]\). Past the end, \(f[n][0] = f[n][1] = 0\).

The number at \(i\) can stay positive, which scores \(\textit{nums}[i] + f[i + 1][1]\). When \(j = 1\) it may also be negated, which scores \(-\textit{nums}[i] + f[i + 1][0]\). \(f[i][j]\) is the larger of the available choices.

We calculate \(f\) from \(i = n - 1\) down to \(0\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[0, 0] for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(2):
                ans = nums[i] + f[i + 1][1]
                if j == 1:
                    ans = max(ans, -nums[i] + f[i + 1][0])
                f[i][j] = ans
        return f[0][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public long maximumTotalCost(int[] nums) {
        int n = nums.length;
        long[][] f = new long[n + 1][2];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < 2; ++j) {
                f[i][j] = nums[i] + f[i + 1][1];
                if (j == 1) {
                    f[i][j] = Math.max(f[i][j], -nums[i] + f[i + 1][0]);
                }
            }
        }
        return f[0][0];
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func maximumTotalCost(nums []int) int64 {
    n := len(nums)
    f := make([][2]int64, n+1)
    for i := n - 1; i >= 0; i-- {
        for j := 0; j < 2; j++ {
            f[i][j] = int64(nums[i]) + f[i+1][1]
            if j == 1 {
                f[i][j] = max(f[i][j], int64(-nums[i])+f[i+1][0])
            }
        }
    }
    return f[0][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maximumTotalCost(nums: number[]): number {
    const n = nums.length;
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(2).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j < 2; ++j) {
            f[i][j] = nums[i] + f[i + 1][1];
            if (j === 1) {
                f[i][j] = Math.max(f[i][j], -nums[i] + f[i + 1][0]);
            }
        }
    }
    return f[0][0];
}

Comments