Skip to main content
Talentd

Maximum Strength of K Disjoint Subarrays - Solution & Explanation

HardArrayDynamic ProgrammingPrefix Sum24 min readAsked at: Amazon, De Shaw
Practice this problem

Problem Statement

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] <= 109
  • 1 <= k <= n
  • 1 <= n * k <= 106
  • k is odd.

Approach Overview

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.

Approach 1: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(k * n^2), Space complexity: O(k * n) where n is the size of nums.

Try this approach in the editor →

Approach 2: Sliding Window and Priority Queue Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n^2 * log k), Space complexity: O(n) used for prefix sums and heap storage.

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time complexity: O(k * n^2), Space complexity: O(k * n) where n is the size of nums.

Sliding Window and Priority Queue Approach

Time complexity: O(n^2 * log k), Space complexity: O(n) used for prefix sums and heap storage.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Prefix SumO(nk)O(nk)General case. Best choice in interviews when selecting k disjoint segments with weighted contributions.
Sliding Window + Priority QueueO(n log n)O(n)Useful when modeling segments as candidate windows and extracting top contributions dynamically.

Video Solution

Maximum Strength of K Disjoint Subarrays | Recursion | Memoization | Leetcode 3077 | Contest 388 • codestorywithMIK • 4,015 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Strength of K Disjoint Subarrays easy or hard?
Maximum Strength of K Disjoint Subarrays is classified as a Hard problem. The challenge comes from combining weighted scoring, multiple disjoint segments, and efficient transitions using dynamic programming and prefix sums.
Maximum Strength of K Disjoint Subarrays Python/Java solution
Most implementations follow the same DP structure across languages. Maintain a DP table indexed by array position and number of segments, compute prefix sums, and update transitions for extending or starting a subarray. The algorithm translates cleanly into Python, Java, C++, C#, and JavaScript.
How to solve Maximum Strength of K Disjoint Subarrays in O(n)?
A strict O(n) solution generally isn't feasible because the algorithm must evaluate transitions for up to k subarrays. The optimal widely used solution runs in O(nk) using dynamic programming with prefix sums. Each step evaluates whether to extend or start a subarray while applying the correct weight.
What is the best approach for Maximum Strength of K Disjoint Subarrays?
Dynamic programming with prefix sums is the most reliable approach. The DP state tracks how many subarrays have been formed and whether the current element extends a segment or starts a new one. Prefix sums allow constant‑time subarray calculations, resulting in an overall time complexity of O(nk).
Is Maximum Strength of K Disjoint Subarrays asked at Google/Amazon/Meta?
Hard dynamic programming problems involving multiple disjoint subarrays appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that maximize k segments or weighted subarray sums test DP state design and prefix sum optimization.
What data structure is used in Maximum Strength of K Disjoint Subarrays?
The main solution relies on arrays for dynamic programming states and prefix sums for constant‑time range sum queries. Some alternative implementations also use a priority queue (heap) to track candidate subarray contributions while maintaining disjoint constraints.
What is the time complexity of Maximum Strength of K Disjoint Subarrays?
The standard dynamic programming solution runs in O(nk) time, where n is the array length and k is the number of required subarrays. Each element updates DP states for all segment counts up to k. Space complexity is typically O(nk) or optimized to O(k) with rolling arrays.

Ready to solve this problem?

Practice Maximum Strength of K Disjoint Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Strength of a Group

Next

Partition Array into Disjoint Intervals