Maximum Strength of K Disjoint Subarrays
HardPrompt
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 <= 106kis odd.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves a direct translation of the problem's definition into a recursive function. The function explores all possible ways to partition the array into k disjoint subarrays and calculates the strength for each combination, returning the maximum one. It does not use any form of memoization, leading to exponential time complexity.
Algorithm
- Define a recursive function
solve(i, j)that computes the maximum strength usingjsubarrays from the prefixnums[0...i-1]. - The base cases for the recursion are:
- If
j == 0, we have selected 0 subarrays, so the strength is 0. - If
i < j, it's impossible to selectjnon-empty disjoint subarrays fromielements, so we return a very small number (negative infinity) to indicate an invalid state.
- If
- For the recursive step
solve(i, j), consider two possibilities:- The
jsubarrays are all contained within the prefixnums[0...i-2]. The strength in this case issolve(i-1, j). - The
j-th subarray ends at indexi-1. We must find the optimal starting positionp-1for this subarray. We iteratepfrom1toi. The strength issolve(p-1, j-1) + C_j * sum(nums[p-1...i-1]), whereC_jis the coefficient for thej-th subarray.
- The
- The result of
solve(i, j)is the maximum of all these possibilities. - The final answer is
solve(n, k).
Walkthrough
The core idea is to define a function, say solve(i, j), which calculates the maximum strength considering the first i elements of nums and selecting exactly j subarrays. To compute solve(i, j), we explore two main choices:
- Don't use
nums[i-1]in thej-th subarray: The optimal solution forjsubarrays must be found within the firsti-1elements. This corresponds to a recursive callsolve(i-1, j). - The
j-th subarray ends atnums[i-1]: We iterate through all possible start indicesp-1(from0toi-1) for this last subarray. For eachp, the firstj-1subarrays must be chosen fromnums[0...p-2]. The strength is calculated by adding the strength from the firstj-1subarrays (solve(p-1, j-1)) and the strength of the newj-th subarray (C_j * sum(nums[p-1...i-1])).
The function returns the maximum value found among all these possibilities. This method is conceptually simple but computationally expensive because it re-solves the same subproblems (solve(i', j') for smaller i' and j') multiple times.
// NOTE: This is a conceptual implementation and will TLE.class Solution { long[] prefix; int n, k; long negInf = Long.MIN_VALUE / 2; public long maximumStrength(int[] nums, int k) { this.n = nums.length; this.k = k; this.prefix = new long[n + 1]; for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + nums[i]; } return solve(n, k); } private long solve(int i, int j) { if (j == 0) { return 0; } if (i < j) { return negInf; } long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1); // Case 1: j subarrays are within nums[0...i-2] long res = solve(i - 1, j); // Case 2: j-th subarray ends at i-1 for (int p = j; p <= i; p++) { long prevStrength = solve(p - 1, j - 1); if (prevStrength > negInf) { long currentSum = prefix[i] - prefix[p - 1]; res = Math.max(res, prevStrength + coeff * currentSum); } } return res; }}Complexity
Time
Exponential, likely O(n^k) or worse. This is because the function branches out extensively without reusing results of solved subproblems.
Space
O(n + k) for the recursion stack depth.
Trade-offs
Pros
Simple to understand and follows the problem definition directly.
Cons
Extremely inefficient due to a massive number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.
The recursion depth can be large, potentially leading to a stack overflow error for large
nork.
This approach improves upon the naive recursion by using dynamic programming to avoid recomputing subproblems. We use a 2D array, dp[i][j], to store the maximum strength achievable from the first i elements using j subarrays. The solution can be implemented either top-down with memoization (by storing the results of the recursive calls) or bottom-up by filling the DP table iteratively. The state transition involves a nested loop, leading to a polynomial but still inefficient time complexity.
Algorithm
- Precompute the prefix sums of the
numsarray to quickly calculate subarray sums. - Create a 2D DP table,
dp[i][j], to store the maximum strength usingjsubarrays from the prefixnums[0...i-1]. - Initialize
dp[i][0] = 0for alli(0 strength for 0 subarrays) and otherdpentries to negative infinity. - Iterate through the number of subarrays
jfrom1tok. - For each
j, iterate through the array indexifrom1ton. - The value
dp[i][j]is the maximum of two cases:- The
jsubarrays are chosen fromnums[0...i-2], so the value isdp[i-1][j]. - The
j-th subarray ends at indexi-1. We find the best starting indexp-1by iteratingpfrom1toi. The strength isdp[p-1][j-1] + C_j * (prefix[i] - prefix[p-1]).
- The
- After filling the table,
dp[n][k]holds the final answer.
Walkthrough
We define dp[i][j] as the maximum strength from nums[0...i-1] using j subarrays. The DP transition is as follows:
dp[i][j] = max(dp[i-1][j], max_strength_ending_at_i)
Here, dp[i-1][j] represents the case where the j subarrays are all within nums[0...i-2]. max_strength_ending_at_i is the maximum strength if the j-th subarray ends at i-1. This is calculated by trying all possible start points p-1 for the last subarray:
max_strength_ending_at_i = max_{1 <= p <= i} (dp[p-1][j-1] + C_j * sum(nums[p-1...i-1]))
By pre-calculating prefix sums, sum(nums[p-1...i-1]) can be found in O(1). The three nested loops (over j, i, and p) give this approach its O(n^2 * k) time complexity.
import java.util.Arrays; class Solution { public long maximumStrength(int[] nums, int k) { int n = nums.length; long[] prefix = new long[n + 1]; for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + nums[i]; } long negInf = Long.MIN_VALUE / 2; long[][] dp = new long[n + 1][k + 1]; for (long[] row : dp) { Arrays.fill(row, negInf); } for (int i = 0; i <= n; i++) { dp[i][0] = 0; } for (int j = 1; j <= k; j++) { long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1); for (int i = j; i <= n; i++) { // Case 1: j subarrays are in nums[0...i-2] long option1 = dp[i - 1][j]; // Case 2: j-th subarray ends at i-1 long maxStrengthEndingAtI = negInf; for (int p = j; p <= i; p++) { // j-th subarray is nums[p-1...i-1] // j-1 subarrays are in nums[0...p-2] if (dp[p - 1][j - 1] > negInf) { long currentSum = prefix[i] - prefix[p - 1]; maxStrengthEndingAtI = Math.max(maxStrengthEndingAtI, dp[p - 1][j - 1] + coeff * currentSum); } } dp[i][j] = Math.max(option1, maxStrengthEndingAtI); } } return dp[n][k]; }}Complexity
Time
O(n^2 * k) due to three nested loops.
Space
O(n * k) to store the DP table.
Trade-offs
Pros
A significant improvement over naive recursion.
Guaranteed to find the optimal solution.
Systematic and easier to debug than a complex recursive solution.
Cons
The time complexity of O(n^2 * k) is too high for the given constraints and will likely result in a TLE.
The space complexity of O(n * k) can also be large, though it might fit within memory limits.
This is the most efficient approach, which optimizes the O(n^2 * k) DP solution. By rewriting the DP recurrence, we can observe that the inner loop, which iterates to find the best split point, is redundant. Its result can be calculated in O(1) time by maintaining a running maximum. This optimization reduces the time complexity to O(n * k). Additionally, space can be optimized to O(n) since computing the DP values for j subarrays only requires the values for j-1 subarrays.
Algorithm
- Precompute the prefix sums of the
numsarray. - Use two arrays,
dpandprev_dp, of sizen+1to store the DP states for the current (j) and previous (j-1) number of subarrays, respectively. This optimizes space from O(n*k) to O(n). - Initialize
prev_dp(forj=0) with all zeros. - Loop
jfrom1tok:- Inside the loop, calculate the coefficient
C_j. - Initialize a variable
max_prev_termto negative infinity. This will track the running maximum of the optimized term. - Loop
ifrom1ton:- Update
max_prev_term = max(max_prev_term, prev_dp[i-1] - C_j * prefix[i-1]). - Calculate the maximum strength with the
j-th subarray ending ati-1:strength_ending_at_i = C_j * prefix[i] + max_prev_term. - Update
dp[i] = max(dp[i-1], strength_ending_at_i).
- Update
- After the inner loop,
prev_dpis updated todpfor the next iteration ofj.
- Inside the loop, calculate the coefficient
- The final answer is the last element of the
dparray afterkiterations,dp[n].
Walkthrough
The key to optimization lies in the recurrence relation for dp[i][j]. The term for calculating the max strength with the j-th subarray ending at i-1 is:
max_{1 <= p <= i} (dp[p-1][j-1] + C_j * (prefix[i] - prefix[p-1]))
We can rearrange this to:
C_j * prefix[i] + max_{1 <= p <= i} (dp[p-1][j-1] - C_j * prefix[p-1])
As we iterate i from 1 to n (for a fixed j), the term max_{1 <= p <= i} (...) can be updated in O(1) time. We maintain a variable, max_prev_term, that keeps track of the maximum value of dp[p-1][j-1] - C_j * prefix[p-1] seen so far. This eliminates the innermost loop over p, bringing the time complexity down to O(n * k). The space is optimized by noticing that dp[...][j] only depends on dp[...][j-1], so we only need to store the DP states for the current and previous number of subarrays.
import java.util.Arrays; class Solution { public long maximumStrength(int[] nums, int k) { int n = nums.length; long[] prefix = new long[n + 1]; for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + nums[i]; } long[] dp = new long[n + 1]; long negInf = Long.MIN_VALUE / 2; for (int j = 1; j <= k; j++) { long[] prevDp = dp; dp = new long[n + 1]; Arrays.fill(dp, negInf); long maxPrevTerm = negInf; long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1); for (int i = j; i <= n; i++) { // Update the running maximum of (prev_dp[p-1] - coeff * prefix[p-1]) for p up to i if (prevDp[i - 1] > negInf) { maxPrevTerm = Math.max(maxPrevTerm, prevDp[i - 1] - coeff * prefix[i - 1]); } // Calculate max strength with j-th subarray ending at i-1 if (maxPrevTerm > negInf) { long strengthEndingAtI = coeff * prefix[i] + maxPrevTerm; dp[i] = Math.max(dp[i - 1], strengthEndingAtI); } else { dp[i] = dp[i-1]; } } } return dp[n]; }}Complexity
Time
O(n * k), because of the two nested loops over `j` (subarrays) and `i` (elements).
Space
O(n), as we only need to store DP states for the current and previous number of subarrays.
Trade-offs
Pros
Highly efficient with O(n * k) time complexity, which passes the given constraints.
Optimal space complexity of O(n).
Provides a structured way to solve a complex optimization problem.
Cons
The logic is more complex and less intuitive than the straightforward DP approach.
Requires careful handling of indices and state transitions to implement correctly.
Solutions
Solution
class Solution {public long maximumStrength(int[] nums, int k) { int n = nums.length; long[][][] f = new long[n + 1][k + 1][2]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { Arrays.fill(f[i][j], Long.MIN_VALUE / 2); } } f[0][0][0] = 0; for (int i = 1; i <= n; i++) { int x = nums[i - 1]; for (int j = 0; j <= k; j++) { long sign = (j & 1) == 1 ? 1 : -1; long val = sign * x * (k - j + 1); f[i][j][0] = Math.max(f[i - 1][j][0], f[i - 1][j][1]); f[i][j][1] = Math.max(f[i][j][1], f[i - 1][j][1] + val); if (j > 0) { long t = Math.max(f[i - 1][j - 1][0], f[i - 1][j - 1][1]) + val; f[i][j][1] = Math.max(f[i][j][1], t); } } } return Math.max(f[n][k][0], f[n][k][1]); }}class Solution {public: long long maximumStrength(vector<int> &nums, int k) { int n = nums.size(); long long f[n + 1][k + 1][2]; memset(f, -0x3f3f3f3f3f3f3f3f, sizeof(f)); f[0][0][0] = 0; for (int i = 1; i <= n; i++) { int x = nums[i - 1]; for (int j = 0; j <= k; j++) { long long sign = (j & 1) == 1 ? 1 : -1; long long val = sign * x * (k - j + 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] + val); if (j > 0) { long long t = max(f[i - 1][j - 1][0], f[i - 1][j - 1][1]) + val; f[i][j][1] = max(f[i][j][1], t); } } } return max(f[n][k][0], f[n][k][1]); }};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 ])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.