LeetCode 3077 - Maximum Strength of K Disjoint Subarrays

The problem is asking us to select exactly k disjoint subarrays from a given array nums such that the last element of each subarray comes before the first element of the next subarray.

leetcodehardarraydynamic-programmingprefix-sum

LeetCode Problem 3077

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem is asking us to select exactly k disjoint subarrays from a given array nums such that the last element of each subarray comes before the first element of the next subarray. The goal is to maximize a weighted sum called strength, where the weight decreases by 1 for each subsequent subarray and alternates in sign as a consequence of the formula:

strength = k * sum(sub1) - (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... ± sum(subk)

Here, sum(subi) is the sum of elements in the i-th subarray. The array elements can be positive, negative, or zero, and k is always an odd positive integer. The input array length n can be up to 10^4, and the product n * k is guaranteed to be no more than 10^6, which allows us to consider some quadratic solutions, but an O(n^3) brute-force approach would be too slow.

The key challenge is handling the disjoint subarrays requirement efficiently while computing a weighted sum that depends on the order and number of subarrays selected. Important edge cases include arrays with all negative numbers, k = 1 (single subarray), or k = n (must select every element as a separate subarray).

Approaches

Brute Force Approach

A brute-force solution would attempt to enumerate all possible ways to select k disjoint subarrays. For each combination, we would compute the weighted strength according to the formula. This guarantees correctness because we are considering all possibilities, but it is extremely inefficient because the number of combinations grows exponentially with n and k.

The main bottleneck is that generating all disjoint subarrays combinations has combinatorial complexity, roughly O(n^k), and computing the sums adds extra overhead. This is impractical for n = 10^4 and k up to n.

Optimal Approach

The key insight is to use dynamic programming with prefix sums. We define dp[i][j] as the maximum strength achievable using the first i elements of nums and selecting exactly j subarrays. The transition considers either extending the current subarray or starting a new subarray at position i. We also use the fact that the weight for the j-th subarray is k - j + 1, allowing us to compute the weighted contribution dynamically.

To compute subarray sums efficiently, we maintain prefix sums so that sum(nums[l..r]) = prefix[r+1] - prefix[l]. For each i, we try to end a subarray at i and update dp[i][j] using the best previous state for dp[l][j-1]. This reduces the problem from exponential to polynomial, typically O(n^2 * k), which is feasible for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^k) O(k) Enumerates all combinations of k disjoint subarrays
Optimal O(n^2 * k) O(n * k) Uses DP with prefix sums to efficiently compute weighted strength

Algorithm Walkthrough

  1. Compute the prefix sum array prefix where prefix[i] is the sum of nums[0..i-1]. This allows O(1) subarray sum queries.
  2. Initialize a DP table dp of size (n+1) x (k+1), filled with -inf, where dp[i][j] represents the maximum strength using first i elements and selecting j subarrays. Set dp[0][0] = 0 as the base case.
  3. Iterate over all i from 1 to n, representing the current end of the subarray.
  4. For each i, iterate over j from 1 to k, representing the number of subarrays selected so far.
  5. For each i and j, iterate over all possible start indices l from 0 to i-1 and calculate the subarray sum s = prefix[i] - prefix[l].
  6. Update dp[i][j] with max(dp[i][j], dp[l][j-1] + weight(j) * s), where weight(j) = k - j + 1.
  7. The final result is the maximum value among dp[i][k] for all i in [1..n].

Why it works: The DP maintains the invariant that dp[i][j] always stores the maximum achievable strength using exactly j subarrays from the first i elements. By considering all possible subarray ends and using prefix sums, we guarantee that no valid combination is missed.

Python Solution

from typing import List

class Solution:
    def maximumStrength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]

        dp = [[float('-inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        for i in range(1, n + 1):
            for j in range(1, k + 1):
                for l in range(i):
                    s = prefix[i] - prefix[l]
                    weight = k - j + 1
                    dp[i][j] = max(dp[i][j], dp[l][j-1] + weight * s)

        return max(dp[i][k] for i in range(1, n + 1))

The Python solution uses a 2D DP table where rows correspond to prefix lengths and columns correspond to the number of subarrays selected. The nested loop computes the best subarray ending at each position, ensuring we respect disjointness. Prefix sums allow O(1) subarray sum computations, avoiding recomputation.

Go Solution

func maximumStrength(nums []int, k int) int64 {
    n := len(nums)
    prefix := make([]int64, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + int64(nums[i])
    }

    dp := make([][]int64, n+1)
    for i := range dp {
        dp[i] = make([]int64, k+1)
        for j := range dp[i] {
            dp[i][j] = -1 << 60
        }
    }
    dp[0][0] = 0

    for i := 1; i <= n; i++ {
        for j := 1; j <= k; j++ {
            for l := 0; l < i; l++ {
                s := prefix[i] - prefix[l]
                weight := int64(k - j + 1)
                candidate := dp[l][j-1] + weight*s
                if candidate > dp[i][j] {
                    dp[i][j] = candidate
                }
            }
        }
    }

    result := int64(-1 << 60)
    for i := 1; i <= n; i++ {
        if dp[i][k] > result {
            result = dp[i][k]
        }
    }
    return result
}

The Go implementation mirrors the Python logic but uses int64 to safely handle large sums and weights. Initialization uses -1 << 60 as negative infinity to avoid integer overflow.

Worked Examples

Example 1: nums = [1,2,3,-1,2], k = 3

Prefix sum: [0,1,3,6,5,7]

DP updates:

i j Best subarray end dp[i][j]
1 1 0-0 3*1 = 3
2 1 0-1 3*3 = 9
3 1 0-2 3*6 = 18
4 2 3-3 18 + (-2)*(-1) = 20
5 3 4-4 20 + 1*2 = 22

Final result: 22

Example 2: nums = [12,-2,-2,-2,-2], k = 5

Select single elements as subarrays, compute 5*12 - 4*(-2) + 3*(-2) - 2*(-2) + (-2) = 64.

Example 3: nums = [-1,-2,-3], k = 1

Select [-1] as the single subarray. Strength: 1*(-1) = -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 * k) Three nested loops: end index i, subarray count j, start index l
Space O(n * k) DP table stores maximum strength