Sum of K Subarrays With Length at Least M

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).

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.

1class Solution {2    long[] prefix;3    Long[][] memo;4    int n;5    int m;6    long small_val = Long.MIN_VALUE / 2;7 8    public long maxSum(int[] nums, int k, int m) {9        this.n = nums.length;10        this.m = m;11        this.prefix = new long[n + 1];12        for (int i = 0; i < n; i++) {13            prefix[i + 1] = prefix[i] + nums[i];14        }15        this.memo = new Long[n][k + 1];16        return findMaxSum(0, k);17    }18 19    private long findMaxSum(int i, int j) {20        if (j == 0) {21            return 0;22        }23        if (i >= n || n - i < j * m) {24            return small_val;25        }26        if (memo[i][j] != null) {27            return memo[i][j];28        }29 30        // Option 1: Skip nums[i]31        long res = findMaxSum(i + 1, j);32 33        // Option 2: Start a subarray at i34        for (int p = i + m - 1; p < n; p++) {35            long currentSum = prefix[p + 1] - prefix[i];36            long nextSum = findMaxSum(p + 1, j - 1);37            if (nextSum > small_val) {38                res = Math.max(res, currentSum + nextSum);39            }40        }41        42        return memo[i][j] = res;43    }44}

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

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).

1class Solution {2    public long maxSum(int[] nums, int k, int m) {3        int n = nums.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + nums[i];7        }8 9        long[][] dp = new long[n + 1][k + 1];10        long small_val = Long.MIN_VALUE / 2;11 12        for (int i = 0; i <= n; i++) {13            for (int j = 1; j <= k; j++) {14                dp[i][j] = small_val;15            }16        }17 18        for (int j = 1; j <= k; j++) {19            long maxPrevDpTerm = small_val;20            for (int i = 1; i <= n; i++) {21                // Case 1: Don't use nums[i-1] in the last subarray22                dp[i][j] = dp[i - 1][j];23                24                // Case 2: nums[i-1] is the end of the j-th subarray25                if (i >= m) {26                    // Update the max term needed for the recurrence27                    maxPrevDpTerm = Math.max(maxPrevDpTerm, dp[i - m][j - 1] - prefix[i - m]);28                    29                    if (maxPrevDpTerm > small_val) {30                        dp[i][j] = Math.max(dp[i][j], maxPrevDpTerm + prefix[i]);31                    }32                }33            }34        }35 36        return dp[n][k];37    }38}

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.

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.

1class Solution {2    public long maxSum(int[] nums, int k, int m) {3        int n = nums.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + nums[i];7        }8 9        long[] dp = new long[n + 1]; // Corresponds to dp for j-1 subarrays10        long small_val = Long.MIN_VALUE / 2;11 12        for (int j = 1; j <= k; j++) {13            long[] newDp = new long[n + 1];14            for(int i = 0; i <= n; i++) {15                newDp[i] = small_val;16            }17 18            long maxPrevDpTerm = small_val;19            for (int i = 1; i <= n; i++) {20                // Case 1: Don't use nums[i-1] in the last subarray21                newDp[i] = newDp[i - 1];22                23                // Case 2: nums[i-1] is the end of the j-th subarray24                if (i >= m) {25                    // dp[i-m] holds the result from the (j-1) iteration26                    maxPrevDpTerm = Math.max(maxPrevDpTerm, dp[i - m] - prefix[i - m]);27                    28                    if (maxPrevDpTerm > small_val) {29                        newDp[i] = Math.max(newDp[i], maxPrevDpTerm + prefix[i]);30                    }31                }32            }33            dp = newDp;34        }35 36        return dp[n];37    }38}