Maximum Strength of K Disjoint Subarrays - Video Solutions

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.