Implement the solution to the Maximum Sum Subarray with Non-Overlapping Elements problem using dynamic programming.?

The Maximum Sum Subarray with Non-Overlapping Elements problem states that given an array of integers and a value k, we need to find the maximum sum of k non-overlapping subarrays in the array.

We can solve this problem using dynamic programming by computing the maximum sum subarray with non-overlapping elements considering the first i elements of the array for each value of i. For each i, we will compute the maximum sum of k non-overlapping subarrays ending at i.

Let’s define an array dp where dp[i][j] represents the maximum sum of j non-overlapping subarrays ending at i. For each i, we can compute dp[i][j] using the recurrence relation:

dp[i][j] = max(dp[i-1][j], dp[i-k][j-1] + sum(arr[i-k+1:i+1]))

Here, dp[i-1][j] represents the maximum sum of j non-overlapping subarrays ending at i-1. If we choose not to include the current element (i.e., arr[i]), then the maximum sum of j non-overlapping subarrays ending at i will be equal to dp[i-1][j].

On the other hand, dp[i-k][j-1] + sum(arr[i-k+1:i+1]) represents the maximum sum of j-1 non-overlapping subarrays ending at i-k, plus the sum of the k elements from i-k+1 to i. If we choose to include the current element, then we can only consider the subarrays that end at i-k, since we need non-overlapping subarrays. Therefore, the maximum sum of j non-overlapping subarrays ending at i will be equal to dp[i-k][j-1] + sum(arr[i-k+1:i+1]).

Finally, the answer to the problem will be the maximum value in dp[n-1][k], where n is the length of the array.

Here’s the Java code that implements the above dynamic programming solution to the Maximum Sum Subarray with Non-Overlapping Elements:

public int maxSumSubarray(int[] arr, int k) {
    int n = arr.length;
    int[][] dp = new int[n][k+1];
    
    for (int j = 1; j <= k; j++) {
        for (int i = j-1; i < n; i++) {
            if (j == 1) {
                dp[i][j] = Math.max(arr[i], (i > 0 ? dp[i-1][j] : 0));
            } else {
                dp[i][j] = (i > j-2 ? dp[i-j+1][j-1] : 0) + arr[i];
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
            }
        }
    }
    
    return dp[n-1][k];
}

The time complexity of the above solution is O(nk), where n is the length of the input array and k is the number of non-overlapping subarrays we need to find.