Sum of K Subarrays With Length at Least M

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

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
• -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

C++

#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];
    }
};

Java

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];
    }
}

Kotlin

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]
    }
}

Python

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]

Rust

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]
    }
}

TypeScript

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)