LeetCode Problem 3473

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem gives an integer array nums, together with two integers k and m. We must choose exactly k non-overlapping subarrays, and every chosen subarray must have length at least m. Among all valid choices, we want the maximum possible total sum.

A subarray is a contiguous segment of the array. Non-overlapping means that no index may belong to more than one selected segment. The segments do not have to cover the entire array, and gaps between segments are allowed.

The input consists of:

• nums, the array of integers, which may contain both positive and negative values.
• k, the number of subarrays that must be selected.
• m, the minimum length allowed for each selected subarray.

The output is a single integer representing the largest achievable sum.

The constraints provide important information:

• n = len(nums) is at most 2000.
• m ≤ 3, which is very small.
• We are guaranteed that k ≤ floor(n / m), therefore a valid answer always exists.
• Negative numbers are allowed, so sometimes we are forced to include undesirable elements because exactly k segments must be chosen.

Several edge cases are worth noting. If all numbers are negative, we still must select exactly k subarrays. When m = 1, every element itself is a valid subarray, which reduces the problem to selecting k disjoint segments of arbitrary lengths. When k = floor(n / m), there may be very little freedom in how segments are arranged. A naive approach that only keeps positive segments would fail because exact selection of k segments is mandatory.

Approaches

Brute Force

A brute-force solution would enumerate every possible set of k non-overlapping subarrays whose lengths are at least m. For each candidate set, we would compute the total sum and keep the maximum.

This approach is correct because it examines every valid arrangement, so the best one cannot be missed. Unfortunately, the number of possibilities grows exponentially with the array size. Even for moderate values of n, the number of segment combinations becomes enormous.

Therefore, brute force is impractical for n = 2000.

Key Insight

The important observation is that the decision process has optimal substructure.

Suppose we are processing the array from left to right. If the last selected segment ends at position i, then everything before the start of that segment is independent of the segment itself. Thus, the best answer using j segments and ending at i can be expressed in terms of the best answer using j-1 segments somewhere earlier.

Prefix sums allow segment sums to be computed in constant time. Dynamic programming then records the best value obtainable using a certain number of segments within a prefix of the array.

The transition

$$dp[j][i]$$

represents the maximum sum obtainable using exactly j segments among the first i elements.

To efficiently consider every possible starting point of the last segment, we maintain a running maximum value

$$dp[j-1][t]-prefix[t]$$

which reduces an otherwise cubic solution to quadratic time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates every possible collection of segments
Optimal	O(nk)	O(nk)	Dynamic programming with prefix sums and running maximum

Algorithm Walkthrough

1. Compute the prefix sum array. The value prefix[i] stores the sum of the first i elements. This allows any subarray sum to be obtained in O(1) time.
2. Define dp[j][i] as the maximum total sum obtainable by choosing exactly j valid subarrays among the first i elements.
3. Initialize dp[0][i] = 0 for every i, because selecting zero segments always produces sum zero.
4. Process the number of segments from 1 to k.
5. For each fixed number of segments j, scan positions from left to right.
6. Maintain a variable

best = max(dp[j-1][t] - prefix[t])

over all indices t that are far enough back so that the last segment has length at least m. 7. At position i, there are two possibilities.

• Ignore element i-1, giving value dp[j][i-1].
• End the last segment at position i, giving value

prefix[i] + best

8. Take the larger of those two values and store it in dp[j][i].
9. After filling the table, dp[k][n] is the answer.

Why it works

For every position i, the final segment must begin at some earlier index t with length at least m. The value before that segment must already be an optimal arrangement using j-1 segments. Since every possible t is incorporated into the running maximum best, the transition examines all legal endings of the last segment. Therefore, the dynamic programming table always stores the optimal value.

Python Solution

from typing import List

class Solution:
    def maxSum(self, nums: List[int], k: int, m: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)
        for i, num in enumerate(nums):
            prefix[i + 1] = prefix[i] + num

        NEG_INF = float("-inf")

        dp = [[NEG_INF] * (n + 1) for _ in range(k + 1)]

        for i in range(n + 1):
            dp[0][i] = 0

        for segments in range(1, k + 1):
            best = NEG_INF

            for i in range(1, n + 1):
                dp[segments][i] = dp[segments][i - 1]

                if i >= m:
                    start = i - m
                    best = max(best, dp[segments - 1][start] - prefix[start])

                    candidate = prefix[i] + best
                    dp[segments][i] = max(dp[segments][i], candidate)

        return dp[k][n]

The implementation begins by constructing prefix sums so that any subarray sum can be computed instantly. A dynamic programming table is then created, where rows correspond to the number of chosen segments and columns correspond to prefixes of the array.

The row for zero segments is initialized to zero because selecting nothing has value zero. For each segment count, the array is scanned from left to right. The variable best stores the largest value of dp[segments-1][t] - prefix[t] seen so far. This quantity represents the best state before starting the current segment.

At every position, we either skip the current element or terminate a segment there. The maximum of those possibilities becomes the new table entry. Finally, the answer is stored in dp[k][n].

Go Solution

func maxSum(nums []int, k int, m int) int {
	n := len(nums)

	prefix := make([]int, n+1)
	for i, num := range nums {
		prefix[i+1] = prefix[i] + num
	}

	const NEG_INF int = -1 << 60

	dp := make([][]int, k+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		for j := range dp[i] {
			dp[i][j] = NEG_INF
		}
	}

	for i := 0; i <= n; i++ {
		dp[0][i] = 0
	}

	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}

	for segments := 1; segments <= k; segments++ {
		best := NEG_INF

		for i := 1; i <= n; i++ {
			dp[segments][i] = dp[segments][i-1]

			if i >= m {
				start := i - m

				best = max(best, dp[segments-1][start]-prefix[start])

				candidate := prefix[i] + best
				dp[segments][i] = max(dp[segments][i], candidate)
			}
		}
	}

	return dp[k][n]
}

The Go implementation closely mirrors the Python version. Since Go does not provide negative infinity for integers, a very small constant is used instead. Slices are used for both the prefix array and the dynamic programming table. Integer overflow is not a concern because the maximum possible absolute sum is only 2000 × 10^4 = 2 × 10^7, well within the range of Go's integer type.

Worked Examples

Example 1

Input:

nums = [1,2,-1,3,3,4]
k = 2
m = 2

Prefix sums:

i	prefix[i]
0	0
1	1
2	3
3	2
4	5
5	8
6	12

One Segment

The best values become:

i	dp[1][i]
0	0
1	0
2	3
3	3
4	5
5	8
6	12

The best one-segment choice is the whole array with sum 12.

Two Segments

Scanning again:

i	dp[2][i]
0	0
1	0
2	0
3	0
4	5
5	8
6	13

The optimal arrangement is:

• [1,2], sum = 3
• [3,3,4], sum = 10

Total:

13

Example 2

Input:

nums = [-10,3,-1,-2]
k = 4
m = 1

Since every element can be its own segment, we may select:

Segment	Sum
[-10]	-10
[3]	3
[-1]	-1
[-2]	-2

Total:

-10

which equals

-10 + 3 - 1 - 2 = -10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk)	Each DP row scans the array once
Space	O(nk)	The DP table contains (k+1)(n+1) entries

The dynamic programming table has k+1 rows and n+1 columns. Each cell is processed in constant time because the running maximum removes the need to enumerate all segment starting points. Therefore the total running time is O(nk), which is easily fast enough for n ≤ 2000.

Test Cases

sol = Solution()

assert sol.maxSum([1, 2, -1, 3, 3, 4], 2, 2) == 13      # provided example
assert sol.maxSum([-10, 3, -1, -2], 4, 1) == -10       # every element separate
assert sol.maxSum([5], 1, 1) == 5                      # single element
assert sol.maxSum([-5], 1, 1) == -5                    # single negative element
assert sol.maxSum([1, 2, 3, 4], 1, 2) == 10            # one segment, entire array
assert sol.maxSum([1, -2, 5, 6, -1, 4], 2, 2) == 15    # two profitable segments
assert sol.maxSum([-1, -2, -3, -4], 2, 1) == -3        # forced negative selections
assert sol.maxSum([10, -100, 10, 10], 2, 1) == 30      # separated positive elements
assert sol.maxSum([1, 1, 1, 1, 1, 1], 3, 2) == 6       # maximum number of segments
assert sol.maxSum([4, -1, 2, -1, 2], 1, 3) == 6        # segment length restriction

Test Summary

Test	Why
[1,2,-1,3,3,4], k=2, m=2	Official example
[-10,3,-1,-2], k=4, m=1	Every element becomes a segment
[5], k=1, m=1	Smallest valid input
[-5], k=1, m=1	Single negative value
[1,2,3,4], k=1, m=2	Entire array chosen
[1,-2,5,6,-1,4], k=2, m=2	Two profitable regions
[-1,-2,-3,-4], k=2, m=1	All values negative
[10,-100,10,10], k=2, m=1	Disjoint positive elements
[1,1,1,1,1,1], k=3, m=2	Largest possible number of segments
[4,-1,2,-1,2], k=1, m=3	Minimum length constraint

Edge Cases

All Numbers Are Negative

A common mistake is to assume that segments with negative sums should never be selected. However, the problem requires exactly k subarrays. When all values are negative, some negative segments are unavoidable. The dynamic programming formulation naturally handles this because it never assumes segment sums are positive.

Minimum Length Greater Than One

When m > 1, a segment cannot start arbitrarily close to its end. Off-by-one mistakes are common here. The implementation only updates the running maximum after ensuring that the starting index is at least m positions behind the current endpoint, guaranteeing that every segment satisfies the length requirement.

Maximum Number of Segments

When k = floor(n / m), nearly every element is forced into some segment. There may be very little flexibility in the arrangement. Because the dynamic programming state records exact segment counts rather than at most k segments, the algorithm correctly handles these tightly constrained situations.

Segments Separated by Gaps

The optimal solution does not require consecutive segments to touch each other. Some elements may remain unused. Since dp[segments][i] inherits the value from dp[segments][i-1], the algorithm can skip arbitrary elements and create gaps whenever doing so improves the total sum.