You are given an array of integers nums with length n, and a positive odd integer k.
Select exactly k disjoint subarrays sub1, 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(subi) 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.
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 <= 104-109 <= nums[i] <= 1091 <= k <= n1 <= n * k <= 106k is odd.Problem Overview: You are given an integer array and must select k disjoint subarrays that maximize a special strength value. Each chosen subarray contributes a weighted sum based on its order, so the algorithm must decide both where each segment starts and ends and which segments produce the highest total score.
Approach 1: Dynamic Programming with Prefix Sum (O(nk) time, O(nk) space)
This approach models the problem as a staged decision process using dynamic programming. Precompute a prefix sum array so any subarray sum can be calculated in O(1). Define DP states that track the maximum strength after processing the first i elements while forming j subarrays, along with whether the current element continues an active segment or starts a new one. During iteration, update transitions for extending the current subarray or closing it and starting the next weighted segment.
The key insight is that each subarray contributes a coefficient based on its order (for example (k - j + 1) with alternating signs). While iterating through the array, the DP transition multiplies the current element by the correct coefficient and adds it to the best previous state. This avoids enumerating all possible subarray boundaries. The algorithm runs in O(nk) time because every index updates DP states for up to k segments.
Approach 2: Sliding Window with Priority Queue (O(n log n) time, O(n) space)
An alternative view treats the task as selecting the best weighted subarray contributions while enforcing the disjoint constraint. Iterate through the array while maintaining running sums for candidate windows. A sliding window identifies profitable segments, and a priority queue stores candidate contributions ordered by strength.
Whenever a window becomes beneficial for the current segment weight, push its contribution into the heap. The heap structure allows quick retrieval of the highest‑value segments while ensuring previously chosen segments remain disjoint. As you move the window forward, outdated candidates are removed and new ones are inserted. Each push or pop operation costs O(log n), producing overall complexity of O(n log n).
Recommended for interviews: The dynamic programming approach is the one most interviewers expect. It clearly demonstrates control over state transitions, weighted scoring, and efficient use of prefix sums. Discussing the heap‑based strategy shows deeper problem exploration, but the DP solution with O(nk) complexity is typically considered the canonical solution.
This approach involves using a dynamic programming table to keep track of the maximum strength possible for each configuration of selecting j subarrays ending at each index i. This table can be filled in by considering at each position the optimal previous configuration plus forming a new subarray ending at that position.
In this C code, we utilize a 2D dynamic programming table where each cell dp[j][i] represents the maximum strength we can achieve with j subarrays ending at index i. We iterate from 1 to k in steps of 2 (since k is odd) and compute the optimal strength by constructing new potential subarrays at each index.
Time complexity: O(k * n^2), Space complexity: O(k * n) where n is the size of nums.
This approach leverages a sliding window technique alongside a priority queue (or heap) to efficiently calculate subarray sums and manage the subarray selection such that the alternating strength function is maximized.
This C implementation utilizes a custom max-heap structure to keep the k largest subarray sums. It generates prefix sums to compute subarray sums in constant time and maintains the heap size at most k. At the end, it greedily selects the largest subarray sums for maximum strength calculation in reverse alternating fashion.
Time complexity: O(n^2 * log k), Space complexity: O(n) used for prefix sums and heap storage.
For the ith number nums[i - 1], if it is selected and is in the jth 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).
We define f[i][j][0] as the maximum energy value when selecting j subarrays from the first i numbers, and the ith number is not selected. We define f[i][j][1] as the maximum energy value when selecting j subarrays from the first i numbers, and the ith number is selected. Initially, f[0][0][1] = 0, and the rest of the values are -infty.
When i > 0, we consider how f[i][j] transitions.
If the ith number is not selected, then the i-1th number can either be selected or not selected, so f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]).
If the ith number is selected, if the i-1th number and the ith number are in the same subarray, then f[i][j][1] = max(f[i][j][1], f[i-1][j][1] + sign times nums[i-1] times (k - j + 1)), otherwise f[i][j][1] = max(f[i][j][1], max(f[i-1][j-1][0], f[i-1][j-1][1]) + sign times nums[i-1] times (k - j + 1)).
The final answer is max(f[n][k][0], f[n][k][1]).
The time complexity is O(n times k), and the space complexity is O(n times k). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time complexity: |
| Sliding Window and Priority Queue Approach | Time complexity: |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sum | O(nk) | O(nk) | General case. Best choice in interviews when selecting k disjoint segments with weighted contributions. |
| Sliding Window + Priority Queue | O(n log n) | O(n) | Useful when modeling segments as candidate windows and extracting top contributions dynamically. |
Maximum Strength of K Disjoint Subarrays | Recursion | Memoization | Leetcode 3077 | Contest 388 • codestorywithMIK • 3,688 views views
Watch 9 more video solutions →Practice Maximum Strength of K Disjoint Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor