#3077

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Strength of K Disjoint Subarrays

Solve Maximum Strength of K Disjoint Subarrays with dynamic programming that tracks segment state, sign changes, and weighted picks.

array dynamic programming prefix sum

Problem Statement

You are given an integer array nums and an odd integer k. You must pick exactly k non-overlapping subarrays in left-to-right order, so once one chosen subarray ends, the next chosen subarray must start later in the array. The goal is not to maximize a plain sum, but to maximize a weighted strength built from the selected subarray sums.

The tricky part is that each chosen subarray contributes with a different coefficient and alternating sign based on its position among the k picks. That means a locally large segment can still be bad if it lands in a negatively weighted slot, so the problem naturally becomes state transition dynamic programming over index, chosen count, and whether a subarray is currently open.

Examples

Constraints

1 <= n <= 104
-109 <= nums[i] <= 109
1 <= k <= n
1 <= n * k <= 106
k is odd.

Solution Approach

Define DP by position, chosen segments, and open state

Use DP to represent the best strength after processing part of nums, after choosing j subarrays, with a flag for whether you are currently inside the j-th subarray. This extra open or closed state is what makes disjointness easy to enforce, because you can only extend an active segment or start a new one from a closed state.

Apply the exact coefficient for each selected subarray

For the t-th selected subarray, its sum is multiplied by a coefficient determined by its order, with alternating sign and decreasing weight. When you add nums[i] into an active segment or start a new segment at i, update the DP using that slot's coefficient immediately. This avoids recomputing subarray sums later and keeps each transition tied to the real strength formula.

Roll transitions efficiently across the array

Process nums from left to right or from suffix to prefix, and update states for taking, extending, closing, or skipping. Since n times k is bounded, an O(nk) style DP with careful state compression is fast enough. The main optimization is storing only the previous layer of states instead of a full 3D table when your transition order allows it.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

A well-structured solution runs in O(nk) time because each array position updates every subarray count state a constant number of ways. Space can be O(k) or O(nk) depending on whether you compress the DP, but the compressed version is usually enough because each transition depends only on the previous index or next suffix layer.

What Interviewers Usually Probe

They want you to notice that Kadane-style greedy fails because each segment has a different signed weight slot.
They expect a DP state that separates closed states from currently extending a chosen subarray.
They are testing whether you can encode the exact strength formula directly into transitions instead of handling sums afterward.

Common Pitfalls or Variants

Common pitfalls

Using a standard maximum k disjoint subarrays DP and forgetting that this problem's coefficients alternate sign and magnitude.
Allowing overlap by starting a new subarray before the previous active subarray has been closed.
Initializing impossible states incorrectly, which lets the DP fake fewer than k picks or open a segment at the wrong stage.

Follow-up variants

Change k from odd-only to any positive integer and keep the same DP shape with adjusted coefficient logic.
Ask for the minimum strength instead of maximum, which flips the optimization direction but keeps the transition structure.
Require returning the actual k subarray boundaries, which adds parent tracking on top of the same DP states.

FAQ

What is the main pattern in Maximum Strength of K Disjoint Subarrays?

The core pattern is state transition dynamic programming. You track index, how many disjoint subarrays have been chosen, and whether the current position belongs to an active chosen subarray.

Why does greedy fail for this problem?

A segment with a large raw sum is not always good because its contribution depends on which selection slot it occupies. Since later or earlier picks can have different signs and weights, local best choices can ruin the final arrangement.

Do I need prefix sums for Maximum Strength of K Disjoint Subarrays?

Prefix sums can help if you write transitions around explicit subarray sums, but many strong solutions fold each value directly into an active-segment DP transition. The important part is not prefix sums alone, but matching them to the weighted pick order correctly.

Why is an open or closed state necessary?

Without it, the DP cannot cleanly distinguish extending the current chosen subarray from starting the next disjoint one. That usually leads to accidental overlap or double counting.

Can this problem be solved in O(nk)?

Yes. The constraint 1 <= n * k <= 10^6 is a strong hint that an O(nk) DP is the intended target, with constant-time transitions per state and optional space compression.

terminal

Solution

Solution 1: Dynamic Programming

For the $i$th number $nums[i - 1]$, if it is selected and is in the $j$th subarray, then its contribution to the answer is $nums[i - 1] \times (k - j + 1) \times (-1)^{j+1}$. We denote $(-1)^{j+1}$ as $sign$, so its contribution to the answer is $sign \times nums[i - 1] \times (k - j + 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumStrength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[[-inf, -inf] for _ in range(k + 1)] for _ in range(n + 1)]
        f[0][0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(k + 1):
                sign = 1 if j & 1 else -1
                f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1])
                f[i][j][1] = max(f[i][j][1], f[i - 1][j][1] + sign * x * (k - j + 1))
                if j:
                    f[i][j][1] = max(
                        f[i][j][1], max(f[i - 1][j - 1]) + sign * x * (k - j + 1)
                    )
        return max(f[n][k])

Continue Practicing

#3225 maximum score from grid operations #3250 find the count of monotonic pairs i #3251 find the count of monotonic pairs ii