We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of K Subarrays With Length at Least M

Number: 3722

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and two integers k and m, the goal is to find the maximum possible sum by selecting exactly k non‐overlapping subarrays from nums such that each chosen subarray has a length of at least m. The subarrays must be contiguous, and their overall sum should be maximized.

Key Insights

  • Use dynamic programming to break the problem into smaller subproblems.
  • Pre-compute a prefix sum array to quickly get subarray sums.
  • Redefine the state so that dp[i][j] is the maximum sum achievable by selecting j subarrays from the first i elements.
  • For each new segment ending at index i-1 with length at least m, combine the best solution ending before its start (using dp[p][j-1]) and add the sum from p to i-1.
  • Optimize the inner loop by maintaining a running maximum of (dp[p][j-1] – prefix_sum[p]) over valid p indices, so that the recurrence becomes: dp[i][j] = max(dp[i-1][j], prefix_sum[i] + best_candidate).

Space and Time Complexity

Time Complexity: O(nk), where n is the length of nums and k is the number of subarrays to choose. Space Complexity: O(nk), for maintaining the dp table and prefix sum array.

Solution

The approach uses dynamic programming with the following ideas:

  1. Create a prefix sum array ps where ps[i] is the sum of the first i elements (with ps[0] = 0). This allows subarray sums to be computed in O(1) time.
  2. Define a DP table dp where dp[i][j] represents the maximum sum possible using j subarrays from the first i elements of nums.
  3. The base case is dp[i][0] = 0 for all i (meaning no segments selected yields sum 0) and dp[0][j] = -∞ for j > 0 (since no elements are available to form a segment).
  4. When forming the j-th subarray, if it ends at index i-1 (i elements considered), then the subarray must have length at least m. Let p represent the starting index of this subarray. The candidate value if we finish a subarray ending at i-1 is dp[p][j-1] + (ps[i] - ps[p]).
  5. Notice that for fixed j and current i the best candidate over valid p (p from (j-1)*m up to i-m) can be maintained in a running variable:   best_candidate = max{ dp[p][j-1] - ps[p] }.
  6. Then dp[i][j] becomes the maximum between not taking a new subarray ending at i-1 (dp[i-1][j]) and starting a new subarray that ends at i-1 (ps[i] + best_candidate).

The final answer is dp[n][k] where n is the length of nums.

Code Solutions

# Python solution for Sum of K Subarrays With Length at Least M

import math

def maxSumOfKSubarrays(nums, k, m):
    n = len(nums)
    # Build prefix sum array: ps[i] = sum(nums[0 .. i-1]); ps[0] = 0.
    ps = [0] * (n + 1)
    for i in range(1, n+1):
        ps[i] = ps[i-1] + nums[i-1]
    
    # Initialize dp table with -infinity for impossible states.
    dp = [[-math.inf] * (k+1) for _ in range(n+1)]
    # Base case: 0 segments yields sum 0.
    for i in range(n+1):
        dp[i][0] = 0

    # For each number of segments from 1 to k:
    for seg in range(1, k+1):
        # best_candidate will keep track of max{ dp[p][seg-1] - ps[p] } over valid p.
        best_candidate = -math.inf
        # i must be at least seg*m to be able to use seg segments.
        for i in range(seg * m, n+1):
            # Update best_candidate with the new possible p = i-m if valid.
            # p must be at least (seg-1)*m and at most i-m.
            p = i - m
            if p >= (seg-1) * m:
                best_candidate = max(best_candidate, dp[p][seg-1] - ps[p])
            # Option 1: Do not end a new segment at i-1, carry forward previous value.
            # Option 2: End a segment at i-1 using the best candidate.
            candidate = ps[i] + best_candidate
            dp[i][seg] = max(dp[i-1][seg], candidate)
    
    return dp[n][k]

# Example usage:
if __name__ == "__main__":
    print(maxSumOfKSubarrays([1,2,-1,3,3,4], 2, 2))  # Expected output: 13
    print(maxSumOfKSubarrays([-10,3,-1,-2], 4, 1))    # Expected output: -10
← Back to All Questions