Problem

You are given an array of integers nums with length n, and a positive odd integer k.

Select exactly k disjoint subarrays sub 1, sub2, ..., subk from nums such that the last element of subi appears before the first element of sub{i+1} for all 1 <= i <= k-1. The goal is to maximize their combined strength.

The strength of the selected subarrays is defined as:

`strength = k * sum(sub1)- (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - … - 2

  • sum(sub{k-1}) + sum(subk)`

where sum(sub i) is the sum of the elements in the i-th subarray.

Return the maximum possible strength that can be obtained from selecting exactly k disjoint subarrays from nums.

Note that the chosen subarrays don ’t need to cover the entire array.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: nums = [1,2,3,-1,2], k = 3

Output: 22

Explanation:

The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and
nums[4..4]. The strength is calculated as follows:

`strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22`

Example 2

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


Input: nums = [12,-2,-2,-2,-2], k = 5

Output: 64

Explanation:

The only possible way to select 5 disjoint subarrays is: nums[0..0],
nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is calculated
as follows:

`strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64`

Example 3

1
2
3
4
5
6
7
8


Input: nums = [-1,-2,-3], k = 1

Output: -1

Explanation:

The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.

Constraints

  • 1 <= n <= 10^4
  • -109 <= nums[i] <= 10^9
  • 1 <= k <= n
  • 1 <= n * k <= 10^6
  • k is odd.

Solution

Method 1 – Dynamic Programming with Alternating Signs

Intuition

The problem requires selecting exactly k disjoint subarrays with alternating signs in their contribution to the total strength. This is similar to a variant of the maximum subarray sum problem, but with alternating coefficients. We use dynamic programming to keep track of the best possible strength for each number of subarrays selected and each sign.

Approach

  1. Let dp[i][j] be the maximum strength using the first i elements and selecting j subarrays.
  2. For each position, try to start a new subarray or extend the previous one, alternating the sign as per the formula.
  3. Use a rolling array to optimize space, since only the previous state is needed.
  4. The sign for the j-th subarray is k-j+1 (positive if odd, negative if even).
  5. Return the maximum value for exactly k subarrays.

Code

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

class Solution {
public:
    long long maximumStrength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<long long>> dp(k+1, vector<long long>(n+1, LLONG_MIN));
        for (int i = 0; i <= n; ++i) dp[0][i] = 0;
        for (int t = 1; t <= k; ++t) {
            long long cur = LLONG_MIN;
            int sign = (k-t+1)%2 ? 1 : -1;
            for (int i = t; i <= n; ++i) {
                cur = max(cur, dp[t-1][i-1]);
                dp[t][i] = max(dp[t][i-1] + sign*nums[i-1], cur + sign*nums[i-1]);
            }
        }
        return *max_element(dp[k].begin(), dp[k].end());
    }
};
 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
27
28

import "math"
func maximumStrength(nums []int, k int) int64 {
    n := len(nums)
    dp := make([][]int64, k+1)
    for i := range dp {
        dp[i] = make([]int64, n+1)
        for j := range dp[i] {
            dp[i][j] = math.MinInt64
        }
    }
    for i := 0; i <= n; i++ { dp[0][i] = 0 }
    for t := 1; t <= k; t++ {
        cur := int64(math.MinInt64)
        sign := int64(1)
        if (k-t+1)%2 == 0 { sign = -1 }
        for i := t; i <= n; i++ {
            if dp[t-1][i-1] > cur { cur = dp[t-1][i-1] }
            a := dp[t][i-1] + sign*int64(nums[i-1])
            b := cur + sign*int64(nums[i-1])
            if a > b { dp[t][i] = a } else { dp[t][i] = b }
        }
    }
    ans := dp[k][0]
    for i := 1; i <= n; i++ {
        if dp[k][i] > ans { ans = dp[k][i] }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[][] dp = new long[k+1][n+1];
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j] = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) dp[0][i] = 0;
        for (int t = 1; t <= k; t++) {
            long cur = Long.MIN_VALUE;
            int sign = ((k-t+1)%2 == 1) ? 1 : -1;
            for (int i = t; i <= n; i++) {
                cur = Math.max(cur, dp[t-1][i-1]);
                dp[t][i] = Math.max(dp[t][i-1] + sign*nums[i-1], cur + sign*nums[i-1]);
            }
        }
        long ans = dp[k][0];
        for (int i = 1; i <= n; i++) ans = Math.max(ans, dp[k][i]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumStrength(nums: IntArray, k: Int): Long {
        val n = nums.size
        val dp = Array(k+1) { LongArray(n+1) { Long.MIN_VALUE } }
        for (i in 0..n) dp[0][i] = 0L
        for (t in 1..k) {
            var cur = Long.MIN_VALUE
            val sign = if ((k-t+1)%2 == 1) 1L else -1L
            for (i in t..n) {
                cur = maxOf(cur, dp[t-1][i-1])
                dp[t][i] = maxOf(dp[t][i-1] + sign*nums[i-1], cur + sign*nums[i-1])
            }
        }
        return dp[k].maxOrNull()!!
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maximumStrength(self, nums: list[int], k: int) -> int:
        n = len(nums)
        dp = [[float('-inf')] * (n+1) for _ in range(k+1)]
        for i in range(n+1):
            dp[0][i] = 0
        for t in range(1, k+1):
            cur = float('-inf')
            sign = 1 if (k-t+1)%2 == 1 else -1
            for i in range(t, n+1):
                cur = max(cur, dp[t-1][i-1])
                dp[t][i] = max(dp[t][i-1] + sign*nums[i-1], cur + sign*nums[i-1])
        return max(dp[k])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn maximum_strength(nums: Vec<i32>, k: i32) -> i64 {
        let n = nums.len();
        let k = k as usize;
        let mut dp = vec![vec![i64::MIN; n+1]; k+1];
        for i in 0..=n { dp[0][i] = 0; }
        for t in 1..=k {
            let sign = if (k-t+1)%2 == 1 { 1 } else { -1 };
            let mut cur = i64::MIN;
            for i in t..=n {
                cur = cur.max(dp[t-1][i-1]);
                dp[t][i] = (dp[t][i-1] + sign*nums[i-1] as i64).max(cur + sign*nums[i-1] as i64);
            }
        }
        *dp[k].iter().max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maximumStrength(nums: number[], k: number): number {
        const n = nums.length;
        const dp: number[][] = Array.from({length: k+1}, () => Array(n+1).fill(-Infinity));
        for (let i = 0; i <= n; ++i) dp[0][i] = 0;
        for (let t = 1; t <= k; ++t) {
            let cur = -Infinity;
            const sign = (k-t+1)%2 === 1 ? 1 : -1;
            for (let i = t; i <= n; ++i) {
                cur = Math.max(cur, dp[t-1][i-1]);
                dp[t][i] = Math.max(dp[t][i-1] + sign*nums[i-1], cur + sign*nums[i-1]);
            }
        }
        return Math.max(...dp[k]);
    }
}

Complexity

  • ⏰ Time complexity: O(kn^2), where n is the length of nums and k is the number of subarrays. Each DP state is filled in O(n) for each k.
  • 🧺 Space complexity: O(kn), for the DP table.