Magic happens when you do not give up, even
though you want to. The universe always falls
in love with a stubborn heart.
Maximum Sum Of M Non-overlapping Subarrays
Welcome Back Reader!
In this article we will discuss about the first problem based on "Dynamic
Programming" i.e. "Maximum Sum Of M Non-overlapping Subarrays".
Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.
In this problem you are given an array (arr) of positive numbers and two
numbers M and K. The size of the given array(arr) is greater than M*K.
All you are required to do is find the maximum sum of M non-overlapping
subarrays of size K.
How?
Given input implies; N = 7, arr = {2 10 7 18 5 33 0}, M = 3, K = 1.
Therefore three subarrays of size 1 which will produce maximum sum are
{10}, {18} and {33}.
For more clarity of the question, watch part of the video.
Approach:
Moving On:
In this problem we need to find the maximum sum of M non-overlapping
subarrays of size K.
So to solve this, first of all we will try to draw the recursion tree for this
problem. Then with the help of a recursion tree, we will build the
memorization approach.
Recursive approach:
At any time the value will have two options i.e. it can either be a part of the
answer or not.
If the value becomes the part of the answer then it will pass the rest of the
work to the kth next element and will also send the information that one
subarray has been taken into consideration so now the next element's job
would be to find M-1 subarrays.
But if that value does not become part of the answer then it will pass the
rest of the work to the next element in the array as it is.
To calculate the maximum sum simultaneously, we will prepare a prefix
sum array in advance which will store the sum of next k elements from
arr[i] at prefixSum[i].
Talking of the base case; whenever m becomes equal to 0 that means all the
m subarrays have been taken into consideration. And also if the index
becomes equal (or greater) to array's length which means that all the
elements have been considered. We are done with the rules.
For more clarity of this part; watch part of the video.
Let's try to code this!
Above code is to prepare the prefixSum array. To build this array, first of all store the sum of first k elements at prefixSum[0] using a for loop.
After that fill the rest of the array by simply subtracting the arr[i-1] and adding the arr[i+K-1].
Above code deals with the problem using a recursion approach. First of all, base cases are handled.
Then two recursive calls are made; one that includes and second that doesn't include the element present at vidx of arr.
Both these recursive calls return their maximum sum value which we store in include and exclude variables of type int.
Then finally we will return the max of include or exclude to the main.
For more clarity of this part; watch part of the video.
Memorization approach:
Now we will solve this using Memorization. In this approach there are basically just a few steps that we need to incorporate in the recursive approach to make it a little more efficient.
First of all we will think about storage. To decide the dimensions of the storage we need to check which of the variables are changing in the signatures of the recursive calls. Here we can see that there are two variables that are changing; vidx and m. So our storage will be a 2D array.
Now we also need to pass the storage i.e. 2D array, dp in the signature of the function.
And before making the recursive call, just check if the dp[vidx][m] stored a non zero value or not. If there is a non zero value then it implies that a recursive call for similar signature values has already been made and we can use the same value instead of making recursive calls all over again. So we can simply return the dp[vidx][m].
And the last change will be to put the max of include and exclude (which is basically the answer) at dp[vidx][m].
For more clarity of this part; watch part of the video.
It is advised that you should also try the tabulation approach for this problem on your own.
You can also cross check or take help of the tabulation approach code from the given complete code below.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < arr.length; i++){
arr[i] = scn.nextInt();
}
int m = scn.nextInt();
int k = scn.nextInt();
// System.out.println(solution(arr, m , k));
System.out.println(maxSumTab(arr,m,k));
}
//Recursion Approach:
public static int solution(int[] arr, int m, int k){
int n = arr.length;
int[] prefixSum = new int[n];
for(int i = 0 ; i < k; i++){
prefixSum[0] += arr[i];
}
for(int i = 1; i <= n - k; i++){
prefixSum[i] = prefixSum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
return maxSum(prefixSum, arr, m, k, 0);
}
public static int maxSum(int[] prefixSum, int[] arr, int m , int k, int vidx){
if(m == 0){
return 0;
}
if(vidx >= arr.length){
return 0;
}
//include-exclude call
int include = prefixSum[vidx] + maxSum(prefixSum, arr, m - 1, k, vidx + k);
int exclude = 0 + maxSum(prefixSum, arr, m, k, vidx + 1);
return Math.max(include, exclude);
}
//Memorization approach:
public static int maxSum(int[] prefixSum, int[] arr, int m int k, int vidx, int[][] dp){
if(m == 0){
return 0;
}
if(vidx >= arr.length){
return 0;
}
if(dp[vidx][m] != 0){
return dp[vidx][m];
}
int include = prefixSum[vidx] + maxSum(prefixSum, arr, m - 1, k, vidx + k);
int exclude = 0 + maxSum(prefixSum, arr, m, k, vidx + 1);
dp[vidx][m] = Math.max(include, exclude)
return dp[vidx][m];
}
//Tabulation approach:
public static int maxSumTab(int[] arr, int m, int k){
int[] ssum = new int[arr.length];
for(int i = arr.length - 1; i >= arr.length - k; i--){
ssum[arr.length - 1] += arr[i];
}
for(int i = arr.length - 2; i >= k - 1; i--){
ssum[i] = ssum[i + 1] + arr[i - k + 1] - arr[i + 1];
}
int[][] dp = new int[arr.length + 1][m + 1];
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp[0].length; j++){
dp[i][j] = Math.max(dp[i - 1][j],i - k >= 0 ? dp[i - k][j - 1] + ssum[i - 1] : 0);
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
}
java;
true";
Analysis
Recursion approach:
Time Complexity: O(n^2)
Two recursive calls are made for n elements (length of input array), which makes the time complexity O(n^2).
Space Complexity: O(n)
One n sized 1D array is used to store the prefix sum which makes the space complexity O(n).
Memorization approach:
Time Complexity: O(n^2)
Two recursive calls are made for n elements (length of input array), which makes the time complexity O(n^2). Space Complexity: O(n*k)
One n sized 1D array is used to store the prefix sum and a second 2d array is used as dp of size n x k, which makes the space complexity O(n*k).
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future! Happy Coding!
