Sum of K Subarrays With Length at Least M

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.

A subarray is a contiguous part of an array. Two subarrays are non-overlapping if they do not share any elements.

Input & Output

Example 1 — Basic Case

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

› Output: 8

💡 Note: Choose subarrays [3,4] with sum 7 and [-1,2] with sum 1. Total maximum sum is 7 + 1 = 8.

Example 2 — Minimum Length

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

› Output: 6

💡 Note: Only one subarray needed with length ≥ 3. Choose [-1,3,4] with sum 6, which is better than [2,-1,3] with sum 4.

Example 3 — All Negative

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

› Output: -3

💡 Note: Must choose one subarray of length ≥ 2. Best option is [-1,-2] with sum -3.

Constraints

1 ≤ k ≤ nums.length
1 ≤ m ≤ nums.length
k × m ≤ nums.length
1 ≤ nums.length ≤ 1000
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,-2,3,4,-1,2], k=2 subarrays, each length ≥ m=2

Process

Find k non-overlapping subarrays with length ≥ m that maximize sum

Output

Maximum possible sum: 8 (from subarrays [3,4] and [-1,2])

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently explore all valid combinations of k non-overlapping subarrays

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use dynamic programming with prefix sums to efficiently compute the maximum sum of k non-overlapping subarrays. The optimal approach maintains dp[i][j] representing the maximum sum using j subarrays from the first i elements. Time: O(n²k), Space: O(nk).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n^(2k))	O(k)	Generate all possible combinations of k non-overlapping subarrays with length ≥ m
Dynamic Programming with Prefix Sum	O(n²k)	O(nk)	Use 2D DP with prefix sums to efficiently compute maximum sum of k subarrays

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible starting positions for subarrays
For each combination, check if subarrays are non-overlapping
Calculate sum for valid combinations
Return maximum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all possible starting positions for subarrays

Validate

Check if subarrays are non-overlapping and length ≥ m

Maximize

Track the combination with maximum sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long maxSum = LLONG_MIN;

void backtrack(int* nums, int n, int index, int selectedCount, long long currentSum, int lastEnd, int k, int m) {
    if (selectedCount == k) {
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        return;
    }
    
    if (index >= n || selectedCount + (n - index) / m < k) {
        return;
    }
    
    for (int start = lastEnd; start < n; start++) {
        for (int end = start + m - 1; end < n; end++) {
            if (selectedCount + (n - end - 1) / m >= k - selectedCount - 1) {
                long long subarraySum = 0;
                for (int i = start; i <= end; i++) {
                    subarraySum += nums[i];
                }
                backtrack(nums, n, end + 1, selectedCount + 1, currentSum + subarraySum, end + 1, k, m);
            }
        }
    }
}

long long solution(int* nums, int n, int k, int m) {
    maxSum = LLONG_MIN;
    backtrack(nums, n, 0, 0, 0, 0, k, m);
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k, m;
    scanf("%d", &k);
    scanf("%d", &m);
    
    printf("%lld\n", solution(nums, n, k, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^(2k))

For each of k subarrays, we try all possible start and end positions, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion depth is k for tracking selected subarrays

✓ Linear Space

12.8K Views

Medium Frequency

~35 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler