# Sum of K Subarrays With Length at Least M
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-k-subarrays-with-length-at-least-m)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-k-subarrays-with-length-at-least-m
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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`.

**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`
* `-104 <= nums[i] <= 104`
* `1 <= k <= floor(nums.length / m)`
* `1 <= m <= 3`

# Approaches
## Recursive Approach with Memoization (Top-Down DP)
This approach uses a top-down dynamic programming technique with recursion and memoization. We define a recursive function that explores all possible ways to select `k` valid subarrays. The state of our recursion is `(i, j)`, representing the problem of finding the maximum sum of `j` subarrays from the portion of the array starting at index `i`.
**Time:** O(n² * k). There are O(n * k) states, and each state computation involves a loop that can run up to O(n) times. · **Space:** O(n * k) for the memoization table and recursion stack depth.
**Pros:** Relatively straightforward to formulate from the problem's recursive nature.; Correctly solves the problem for smaller inputs.
**Cons:** The time complexity of O(n² * k) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.; The space complexity of O(n * k) can be large, potentially causing memory issues for large `n` and `k`.
### Explanation
The core idea is to build the solution by making a decision at each index `i` of the array. For a given state `(i, j)`, we have two main options:

1.  **Don't start a subarray at index `i`**: We move to the next index `i+1` and try to find `j` subarrays from there. This corresponds to the recursive call `findMaxSum(i + 1, j)`.
2.  **Start the next subarray at index `i`**: This subarray must have a length of at least `m`. We can try every possible end index `p` from `i + m - 1` to `n - 1`. For each choice of `p`, we form a subarray `nums[i...p]`, calculate its sum, and recursively call the function to find the remaining `j-1` subarrays from index `p+1` onwards (`findMaxSum(p + 1, j - 1)`). We take the maximum value among all possible end points `p`.

The final answer for `(i, j)` is the maximum of these two options. To avoid recomputing results for the same state, we store them in a 2D memoization table. Prefix sums are used to quickly calculate the sum of any subarray.

```java
class Solution {
    long[] prefix;
    Long[][] memo;
    int n;
    int m;
    long small_val = Long.MIN_VALUE / 2;

    public long maxSum(int[] nums, int k, int m) {
        this.n = nums.length;
        this.m = m;
        this.prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        this.memo = new Long[n][k + 1];
        return findMaxSum(0, k);
    }

    private long findMaxSum(int i, int j) {
        if (j == 0) {
            return 0;
        }
        if (i >= n || n - i < j * m) {
            return small_val;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        // Option 1: Skip nums[i]
        long res = findMaxSum(i + 1, j);

        // Option 2: Start a subarray at i
        for (int p = i + m - 1; p < n; p++) {
            long currentSum = prefix[p + 1] - prefix[i];
            long nextSum = findMaxSum(p + 1, j - 1);
            if (nextSum > small_val) {
                res = Math.max(res, currentSum + nextSum);
            }
        }
        
        return memo[i][j] = res;
    }
}
```
### Algorithm
1.  Define a recursive function `findMaxSum(i, j)` which computes the maximum sum of `j` subarrays from the suffix of the array `nums[i:]`.
2.  Use a 2D array `memo[i][j]` for memoization to store the results of `findMaxSum(i, j)`.
3.  The base cases for the recursion are:
    *   If `j == 0`, we need 0 subarrays, so the sum is 0.
    *   If we cannot form `j` subarrays of length `m` from the remaining elements (i.e., `i >= n` or `n - i < j * m`), return a very small number to signify an invalid path.
4.  In the recursive step for `findMaxSum(i, j)`, consider two choices:
    *   **Skip `nums[i]`**: The result is `findMaxSum(i + 1, j)`.
    *   **Start a new subarray at `i`**: Iterate through all possible end points `p` for a subarray starting at `i` (where `p >= i + m - 1`). For each `p`, the sum is `sum(nums[i...p]) + findMaxSum(p + 1, j - 1)`. We take the maximum over all valid `p`.
5.  The final result for `findMaxSum(i, j)` is the maximum of these two choices.
6.  Store the result in `memo[i][j]` before returning.
7.  Pre-calculate prefix sums to compute `sum(nums[i...p])` in O(1) time.
8.  The initial call is `findMaxSum(0, k)`.

## Iterative Dynamic Programming (Bottom-Up DP)
This approach uses bottom-up dynamic programming to solve the problem more efficiently. We build a 2D table, `dp[i][j]`, to store the maximum sum of `j` subarrays considering the first `i` elements of the input array. By optimizing the transition, we can calculate each DP state in constant time, leading to a much better time complexity than the naive recursive solution.
**Time:** O(n * k). The two nested loops for `j` and `i` dominate, and the inner operations are O(1). · **Space:** O(n * k) to store the 2D DP table.
**Pros:** The O(n * k) time complexity is efficient enough to pass the given constraints.; It's a systematic, bottom-up approach that is often easier to debug than recursion.
**Cons:** The O(n * k) space complexity can be substantial for the maximum constraints, potentially leading to memory limit issues.
### Explanation
Let `dp[i][j]` be the maximum sum of `j` non-overlapping subarrays, each of length at least `m`, using the prefix `nums[0...i-1]`.

The transition for `dp[i][j]` is based on two possibilities for the element `nums[i-1]`:

1.  **`nums[i-1]` is not part of the last subarray**: The optimal solution for `j` subarrays in `nums[0...i-1]` is the same as for `nums[0...i-2]`. So, `dp[i][j] = dp[i-1][j]`.
2.  **`nums[i-1]` is the end of the `j`-th subarray**: This subarray, say `nums[p...i-1]`, must have length at least `m`. The other `j-1` subarrays must be chosen from `nums[0...p-1]`. The total sum is `dp[p][j-1] + sum(nums[p...i-1])`. We need to maximize this over all valid start positions `p`.

This leads to the recurrence: `dp[i][j] = max(dp[i-1][j], max_{0 <= p <= i-m} (dp[p][j-1] + prefix[i] - prefix[p]))`.

The term `max_{0 <= p <= i-m} (dp[p][j-1] - prefix[p])` can be computed efficiently. As we iterate `i` from 1 to `n`, we can maintain a running maximum of `dp[q][j-1] - prefix[q]` for `q` up to `i-m`. This optimization reduces the calculation of each DP state to O(1).

```java
class Solution {
    public long maxSum(int[] nums, int k, int m) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long[][] dp = new long[n + 1][k + 1];
        long small_val = Long.MIN_VALUE / 2;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = small_val;
            }
        }

        for (int j = 1; j <= k; j++) {
            long maxPrevDpTerm = small_val;
            for (int i = 1; i <= n; i++) {
                // Case 1: Don't use nums[i-1] in the last subarray
                dp[i][j] = dp[i - 1][j];
                
                // Case 2: nums[i-1] is the end of the j-th subarray
                if (i >= m) {
                    // Update the max term needed for the recurrence
                    maxPrevDpTerm = Math.max(maxPrevDpTerm, dp[i - m][j - 1] - prefix[i - m]);
                    
                    if (maxPrevDpTerm > small_val) {
                        dp[i][j] = Math.max(dp[i][j], maxPrevDpTerm + prefix[i]);
                    }
                }
            }
        }

        return dp[n][k];
    }
}
```
### Algorithm
1.  Pre-calculate the prefix sums of the `nums` array to find subarray sums in O(1).
2.  Create a 2D DP table `dp[n+1][k+1]`, where `dp[i][j]` stores the maximum sum of `j` subarrays within the prefix `nums[0...i-1]`.
3.  Initialize `dp[i][0] = 0` for all `i`, and all other `dp` entries to a very small number.
4.  Iterate `j` from 1 to `k` (number of subarrays).
5.  Inside this loop, iterate `i` from 1 to `n` (length of the prefix).
6.  For each `dp[i][j]`, the value is determined by two cases:
    *   **Case 1**: The `j` subarrays are all within `nums[0...i-2]`. The value is `dp[i-1][j]`.
    *   **Case 2**: The `j`-th subarray ends at `nums[i-1]`. Its sum is `sum(nums[p...i-1])` and the other `j-1` subarrays are in `nums[0...p-1]`. We need to find `max_{0 <= p <= i-m} (dp[p][j-1] + sum(nums[p...i-1]))`.
7.  The recurrence is `dp[i][j] = max(dp[i-1][j], prefix[i] + max_{0 <= p <= i-m} (dp[p][j-1] - prefix[p]))`.
8.  To avoid the inner O(n) loop for `p`, maintain a variable `max_prev_dp_term` that tracks `max(dp[p][j-1] - prefix[p])` as `i` increases.
9.  The final answer is `dp[n][k]`.

## Space-Optimized Iterative DP
This is the most optimized approach. It improves upon the previous DP solution by reducing the space complexity. We observe that when calculating the DP values for `j` subarrays, we only need the results from `j-1` subarrays. This dependency allows us to discard older DP states and use only two 1D arrays to store the results for the previous and current number of subarrays, reducing the space from O(n*k) to O(n).
**Time:** O(n * k). The time complexity is identical to the unoptimized space version. · **Space:** O(n). We use two arrays of size O(n) for the DP states and one O(n) array for prefix sums.
**Pros:** Most efficient solution for the given constraints.; Optimal space complexity of O(n), which is memory-friendly.; Maintains the efficient O(n * k) time complexity.
**Cons:** The implementation can be slightly more complex due to the need to manage and swap two arrays.
### Explanation
The recurrence relation and logic are the same as the standard bottom-up DP. The key difference is in the data structures used. Instead of a full `dp[n+1][k+1]` table, we maintain only the DP results for the current number of subarrays (`j`) and the previous one (`j-1`).

Let `dp` be the array storing results for `j-1` subarrays and `newDp` be the array where we compute results for `j` subarrays. The outer loop iterates `j` from 1 to `k`. In each iteration, we compute the entire `newDp` array using values from the `dp` array. Once `newDp` is fully computed, it contains the optimal sums for `j` subarrays. We then assign `newDp` to `dp` and proceed to the next iteration for `j+1`.

This optimization is crucial for problems where `n` and `k` are large, as it prevents potential memory limit errors while keeping the time complexity the same.

```java
class Solution {
    public long maxSum(int[] nums, int k, int m) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long[] dp = new long[n + 1]; // Corresponds to dp for j-1 subarrays
        long small_val = Long.MIN_VALUE / 2;

        for (int j = 1; j <= k; j++) {
            long[] newDp = new long[n + 1];
            for(int i = 0; i <= n; i++) {
                newDp[i] = small_val;
            }

            long maxPrevDpTerm = small_val;
            for (int i = 1; i <= n; i++) {
                // Case 1: Don't use nums[i-1] in the last subarray
                newDp[i] = newDp[i - 1];
                
                // Case 2: nums[i-1] is the end of the j-th subarray
                if (i >= m) {
                    // dp[i-m] holds the result from the (j-1) iteration
                    maxPrevDpTerm = Math.max(maxPrevDpTerm, dp[i - m] - prefix[i - m]);
                    
                    if (maxPrevDpTerm > small_val) {
                        newDp[i] = Math.max(newDp[i], maxPrevDpTerm + prefix[i]);
                    }
                }
            }
            dp = newDp;
        }

        return dp[n];
    }
}
```
### Algorithm
1.  The overall logic is identical to the previous iterative DP approach.
2.  Instead of a 2D `dp` table, use two 1D arrays: `dp` (for results of `j-1` subarrays) and `newDp` (for results of `j` subarrays).
3.  Initialize `dp` array of size `n+1` with all zeros, representing the base case for `j=0`.
4.  Loop `j` from 1 to `k`.
5.  Inside the loop, initialize `newDp` with a very small value.
6.  Also initialize `max_prev_dp_term` to a very small value. This variable will track `max(dp[p] - prefix[p])`.
7.  Loop `i` from 1 to `n`:
    *   Set `newDp[i] = newDp[i-1]` (Case 1).
    *   If `i >= m`, update `max_prev_dp_term = max(max_prev_dp_term, dp[i-m] - prefix[i-m])`.
    *   If `max_prev_dp_term` is valid, update `newDp[i] = max(newDp[i], max_prev_dp_term + prefix[i])` (Case 2).
8.  After the inner loop over `i` finishes, replace `dp` with `newDp` for the next iteration of `j`.
9.  The final answer is `dp[n]` after the outer loop completes.