Problem

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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= floor(nums.length / m)
  • 1 <= m <= 3

Solution

Method 1 – Dynamic Programming with Prefix Sums

Intuition

To maximize the sum of k non-overlapping subarrays of at least length m, we use dynamic programming. For each position, we consider the best way to select a subarray ending at that position, using prefix sums for efficient range sum calculation. By iteratively building up the solution for increasing numbers of subarrays, we ensure that no subarrays overlap and all have the required minimum length.

Approach

Let dp[i][j] be the max sum for first i elements with j subarrays. For each position, try to start a new subarray of length at least m, and use prefix sums for fast range sum. Since m is small, we can enumerate all possible subarray starts efficiently.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int maxSumOfKSubarrays(vector<int>& nums, int k, int m) {
        int n = nums.size();
        vector<int> pre(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MIN));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j > 0 && i >= m) {
                    for (int l = m; l <= i; ++l) {
                        if (dp[i-l][j-1] != INT_MIN)
                            dp[i][j] = max(dp[i][j], dp[i-l][j-1] + pre[i] - pre[i-l]);
                    }
                }
            }
        }
        return dp[n][k];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    public int maxSumOfKSubarrays(int[] nums, int k, int m) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        int[][] dp = new int[n+1][k+1];
        for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j > 0 && i >= m) {
                    for (int l = m; l <= i; ++l) {
                        if (dp[i-l][j-1] != Integer.MIN_VALUE)
                            dp[i][j] = Math.max(dp[i][j], dp[i-l][j-1] + pre[i] - pre[i-l]);
                    }
                }
            }
        }
        return dp[n][k];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maxSumOfKSubarrays(nums: IntArray, k: Int, m: Int): Int {
        val n = nums.size
        val pre = IntArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]
        val dp = Array(n+1) { IntArray(k+1) { Int.MIN_VALUE } }
        dp[0][0] = 0
        for (i in 1..n) {
            for (j in 0..k) {
                dp[i][j] = dp[i-1][j]
                if (j > 0 && i >= m) {
                    for (l in m..i) {
                        if (dp[i-l][j-1] != Int.MIN_VALUE)
                            dp[i][j] = maxOf(dp[i][j], dp[i-l][j-1] + pre[i] - pre[i-l])
                    }
                }
            }
        }
        return dp[n][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxSumOfKSubarrays(self, nums: list[int], k: int, m: int) -> int:
        n = len(nums)
        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[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(k+1):
                dp[i][j] = dp[i-1][j]
                if j > 0 and i >= m:
                    for l in range(m, i+1):
                        if dp[i-l][j-1] != float('-inf'):
                            dp[i][j] = max(dp[i][j], dp[i-l][j-1] + pre[i] - pre[i-l])
        return dp[n][k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn max_sum_of_k_subarrays(nums: Vec<i32>, k: i32, m: i32) -> i32 {
        let n = nums.len();
        let mut pre = vec![0; n+1];
        for i in 0..n { pre[i+1] = pre[i] + nums[i]; }
        let k = k as usize;
        let m = m as usize;
        let mut dp = vec![vec![i32::MIN; k+1]; n+1];
        dp[0][0] = 0;
        for i in 1..=n {
            for j in 0..=k {
                dp[i][j] = dp[i-1][j];
                if j > 0 && i >= m {
                    for l in m..=i {
                        if dp[i-l][j-1] != i32::MIN {
                            dp[i][j] = dp[i][j].max(dp[i-l][j-1] + pre[i] - pre[i-l]);
                        }
                    }
                }
            }
        }
        dp[n][k]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function maxSumOfKSubarrays(nums: number[], k: number, m: number): number {
    const n = nums.length;
    const pre = new Array(n+1).fill(0);
    for (let i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
    const dp = Array.from({length: n+1}, () => Array(k+1).fill(-Infinity));
    dp[0][0] = 0;
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j <= k; ++j) {
            dp[i][j] = dp[i-1][j];
            if (j > 0 && i >= m) {
                for (let l = m; l <= i; ++l) {
                    if (dp[i-l][j-1] !== -Infinity)
                        dp[i][j] = Math.max(dp[i][j], dp[i-l][j-1] + pre[i] - pre[i-l]);
                }
            }
        }
    }
    return dp[n][k];
}

Complexity

  • ⏰ Time complexity: O(n^2 k)
  • 🧺 Space complexity: O(nk)