Skip to content

3956. Maximum Sum of M Non-Overlapping Subarrays I

SourceWeekly Contest 505 Q3DifficultyHardRating2060

Description

You are given an integer array nums of length n, and three integers m, l, and r.

Your task is to select at least one and at most m non-overlapping subarrays from nums such that:

  • Each selected subarray has a length between [l, r] (inclusive).
  • The total sum of all selected subarrays is maximized.

Return the maximum total sum you can achieve.

 

Example 1:

Input: nums = [4,1,-5,2], m = 2, l = 1, r = 3

Output: 7

Explanation:

One optimal strategy is to:

  • Select the subarray [4, 1] with sum 4 + 1 = 5 and the subarray [2] with sum 2. Both subarrays have length between [l, r].
  • The total sum of these subarrays is 5 + 2 = 7, which is the maximum achievable sum with at most m = 2 subarrays.

Example 2:

Input: nums = [1,0,3,4], m = 2, l = 1, r = 2

Output: 8

Explanation:

One optimal strategy is to:

  • Select the subarray [1] with sum 1 and the subarray [3, 4] with sum 3 + 4 = 7. Both subarrays have length between [l, r].
  • The total sum of these subarrays is 1 + 7 = 8, which is the maximum achievable sum with at most m = 2 subarrays.

Example 3:

Input: nums = [-1,7,-4], m = 1, l = 2, r = 3

Output: 6

Explanation:

  • Select the subarray [-1, 7] from nums which has length between [l, r].
  • The total sum of this subarray is -1 + 7 = 6, which is the maximum achievable sum with at most m = 1 subarray.

Example 4:

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

Output: -1

Explanation:

  • All subarrays of nums have negative sums. The optimal strategy is to select the subarray [-1], which has length between [l, r].
  • The total sum of this subarray is -1, which is the maximum achievable sum with at most m = 2 subarrays.

 

Constraints:

  • 1 <= n == nums.length <= 1000
  • -109 <= nums[i] <= 109​​​​​​​
  • 1 <= m <= n
  • 1 <= l <= r <= n

Solutions

Solution 1

Thinking

At most \(m\) non-overlapping segments of length in \([l,r]\) should maximize the sum of their sums. A DP that also enumerates length is governed by \(n,m,r-l\); part I typically allows \(O(nm(r-l))\) or an \(O(nm)\) prefix-sum form.

Let \(f[i][t]\) be the best sum on the first \(i\) elements with at most \(t\) segments: skip as \(f[i-1][t]\), or end a legal segment \([j,i)\) as \(f[j][t-1]+(s_i-s_j)\). The answer is the best among \(t\ge 1\).

This directory has no implemented solution yet; the walkthrough stops at that partition DP.

1


1


1


1

Comments