No one's coming. No one's coming to push you. You've got to parent yourself, you gotta push yourself up there.
Maximum Sum Of Two Non-overlapping Subarrays
Welcome Back Reader!
In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Maximum Sum Of Two 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.
Understanding the problem:
In this problem you are given an array of positive numbers and two numbers X and Y.
All you have to do is find the maximum sum of elements in two non overlapping subarrays.
One subarray must be of length X and the other must be of length Y.
Sample Input:
9
0 6 5 2 2 5 1 9 4
1
2
Sample Output:
20 How?
First subarray needs to be of length 1 and the second subarray needs to be of length 2. To get the maximum sum, subarray-1 will constitute '9' and subarray-2 will constitute '6' and '5', which sum up to give 20.
For better understanding of the question, watch part of the video lecture.
Approach
To solve this problem we need to use two 1D arrays dp1 and dp2 of length n (input array's length).
First dp array, at any index i will store the maximum sum of X consecutive elements of the input array till index i.
Whereas second dp array, at any index i will store the maximum sum of Y consecutive elements of the input array from index i.
Then we will take help of one more array (sum array) of length n to store the sum of the index of dp1 and (i+1)th index of dp2. And the maximum sum array will be the answer. Is that enough? NOO!
Till now we have only considered the cases when X consecutive elements are present before Y consecutive elements. But there is a possibility that the maximum sum is present in such a way that the Y consecutive elements occur before X consecutives elements.
So to do so we will just repeat the similar steps with slight variation.
First dp array, at any index i will store the maximum sum of Y consecutive elements of the input array till index i.
Whereas second dp array, at any index i will store the maximum sum of X consecutive elements of the input array from index i.
Then we will take help of one more array (sum array-2) of length n to store the sum of ith index of dp1 and (i+1)th index of dp2.
And the maximum of sum array and sum array-2 will be the final answer.
Let's take an example for better understanding. For example:
First of all we will prepare dp1 which will store the maximum sum of 2 consecutive elements of the given array till any index i.
After that we will prepare dp2 which will store the maximum sum of 3 consecutive elements of the given array from any index i.
And then we will prepare a sum array which will store the sum of ith element of dp1 and (i+1)th element of dp2.
Now we need to repeat these steps considering if Y consecutive elements occur before X consecutive elements to give the maximum sum.
So prepare dp1' which will store the maximum sum of 3 consecutive elements of the given array till any index i.
After that we will prepare dp2' which will store the maximum sum of 2 consecutive elements of the given array from any index i.
And then we will prepare a sum array which will store the sum of ith element of dp1' and (i+1)th element of dp2.
The maximum of sum array and sum' array will be the final answer i.e. 29.
For better understanding of the question, watch part of the video lecture.
Let's try to code this!
public static int solution(int[] arr, int x, int y){
int n = arr.length; //1
int[] prefixSum = new int[n + 1]; //2
for(int i = 1; i <= n; i++){ //3
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
int xmax = prefixSum[x];
int ymax = prefixSum[y];
int ans = prefixSum[x + y];
for(int i = x + y; i<= n; i++){
xmax = Math.max(xmax, prefixSum[i - y] - prefixSum[i - (x + y)]);
ymax = Math.max(ymax, prefixSum[i - x] - prefixSum[i - (x + y)]);
ans = Math.max(ans, Math.max(xmax + prefixSum[i] - prefixSum[i - y], ymax + prefixSum[i] - prefixSum[i - x]));
}
return ans;
}
java;
true";
Complete code :
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 x = scn.nextInt();
int y = scn.nextInt();
System.out.println(solution(arr,x,y));
}
public static int solution(int[] arr, int x, int y){
int n = arr.length;
int[] prefixSum = new int[n + 1];
for(int i = 1; i <= n; i++){
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
int xmax = prefixSum[x];
int ymax = prefixSum[y];
int ans = prefixSum[x + y];
for(int i = x + y; i<= n; i++){
xmax = Math.max(xmax, prefixSum[i - y] - prefixSum[i - (x + y)]);
ymax = Math.max(ymax, prefixSum[i - x] - prefixSum[i - (x + y)]);
ans = Math.max(ans, Math.max(xmax + prefixSum[i] - prefixSum[i - y], ymax + prefixSum[i] - prefixSum[i - x]));
}
return ans;
}
}
java;
true";
Complexities:
Time Complexity: O(n)
A for loop is used 6 times to fill the dp arrays 4 times and sum arrays 2 times which condenses to O(n).
Space Complexity: O(n)
Three n sized 1D arrays are used which condenses to O(n).
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.
