Maximum Strength of K Disjoint Subarrays
HardUpdated: Aug 2, 2025
Practice on:
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
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
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
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-10^9 <= nums[i] <= 10^91 <= k <= n1 <= n * k <= 10^6kis 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
- Let
dp[i][j]be the maximum strength using the firstielements and selectingjsubarrays. - For each position, try to start a new subarray or extend the previous one, alternating the sign as per the formula.
- Use a rolling array to optimize space, since only the previous state is needed.
- The sign for the j-th subarray is
k-j+1(positive if odd, negative if even). - Return the maximum value for exactly k subarrays.
Code
C++
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());
}
};
Go
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
}
Java
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;
}
}
Kotlin
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()!!
}
}
Python
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])
Rust
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()
}
}
TypeScript
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), wherenis the length of nums andkis the number of subarrays. Each DP state is filled in O(n) for each k. - 🧺 Space complexity:
O(kn), for the DP table.