Skip to content

3473. Sum of K Subarrays With Length at Least M

SourceWeekly Contest 439 Q3DifficultyMediumRating2274

Description

You are given an integer array nums and two integers, k and m.

Return the maximum sum of k non-overlapping subarrays of nums, where each subarray has a length of at least m.

 

Example 1:

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

Output: 13

Explanation:

The optimal choice is:

  • Subarray nums[3..5] with sum 3 + 3 + 4 = 10 (length is 3 >= m).
  • Subarray nums[0..1] with sum 1 + 2 = 3 (length is 2 >= m).

The total sum is 10 + 3 = 13.

Example 2:

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

Output: -10

Explanation:

The optimal choice is choosing each element as a subarray. The output is (-10) + 3 + (-1) + (-2) = -10.

 

Constraints:

  • 1 <= nums.length <= 2000
  • -104 <= nums[i] <= 104
  • 1 <= k <= floor(nums.length / m)
  • 1 <= m <= 3

Solutions

Solution 1

Thinking

We pick \(k\) non-overlapping subarrays of length at least \(m\) and maximize their total sum. The product of \(n\), \(k\), and \(m\) must stay in a DP range.

Whether we are currently inside a segment has to be part of the state, otherwise the length floor cannot be enforced.

\(f[i][j][0/1]\) considers the first \(i\) elements, \(j\) finished segments, and whether we are inside one. We skip \(i\), or start/extend a segment. The answer is \(f[n][k][*]\).

1


1


1


1

Comments