Code is like humor. When you have to explain it, it's bad.
~Cory House
Maximum Sum of 3 Non-Overlapping Subarrays
Welcome back, dear reader. So, how is it going? In this article, we will solve a very interesting problem called MAXIMUM SUM OF 3 NON-OVERLAPPING SUBARRAYS. So, what does this problem say?
We will be given an input array and an integer K. We have to find 3 non-overlapping subarrays, each of size K from the input arrays whose sum is the maximum. Also, if there are more than one such answers, we have to consider the lexicographically smaller answer. What do we mean by this? Have a look at the image shown below:
As shown above, we are given an array of size 8 and we are also given K=2 i.e. we have to find 3 non-overlapping arrays of size k==2 whose sum is maximum. We have shown two possible answers in this case. Both have the sum 23 i.e. the maximum possible sum for three non-overlapping arrays of size k=2. So, if we ever come across such a situation where multiple answers like the case shown above are possible, we have to consider the starting indices of these subarrays and print the answer that is lexicographically smaller. Since 0,3,5 was lexicographically smaller than 1,3,5 hence we selected it as the solution.
We recommend you refer to the question on the portal once to understand the input and output formats and also, we recommend you refer to the solution video to understand the question if you have any doubts regarding it.
We suggest you try to solve the problem on your own and then go to the solution to build your concepts strong.
Approach
Explaination
Dear reader, we recommend you refer to the MAXIMUM SUM OF 2 NON-OVERLAPPING SUBARRAYS VIDEO as it is going to be the basis for solving this problem.
So, first of all, we will create a dp array in which we will store the maximum sum of the subarrays of size K till a particular index. Let us consider the array given below:
So, let us make the first dp array and assign the storage and meaning to it.
So, this array will store the maximum subarray sum till a particular index where the size of the subarray is K. Let us start filling this array.
Filling the first DP Array
The first two elements will be empty as the size is less than K=3. At index 3, we only have one subarray of size=k=3. So, we will put the sum of that subarray here.
Next, we move to index 3. Here we have two options. The first will be the current K sized window shown in yellow in the array and the other will be the previous maximum window shown in pink color in the array.
The previous maximum value can be taken from dp1[i-1] but the current sum needs to be calculated. The maximum out of them is stored in dp1[i] as shown in the image below:
So, we have to fill this entire array in the same way. We recommend you fill the remaining array yourself. The completely filled array is shown below:
Filling the second DP Array
We will make another dp array that will also be of the same size as that of the array. Each element in that array will store the maximum subarray sum from that particular index till the end of the array and the size of the subarray will be exactly K.
We will start filling this array from the last element. Why? Think!!!
The last 2 elements will remain empty as the size of the subarray should be equal to K. Now, we will start from index i=10. So, there is only one subarray of size K=3 from index 10 till the end of the array. So, dp2[10] will be the sum of these elements only.
Let us move to the index=9 now. Here, we have two subarrays with size K=3. The current window of size K is marked in pink and the previous max subarray marked with yellow. The previous max subarray sum can be taken directly from dp2[i+1] and the current subarray sum needs to be calculated. The maximum out of them will be stored in dp[i].
So, we can fill this entire array in the same way. We recommend you try to fill the remaining array yourself. The completely filled array is shown below:
So, we have actually found the maximum subarray sums for two arrays out of 3 non-overlapping arrays. Let us assume we have found it for the left and the right array. Now, let us try to figure out where we will fit the middle array.
Locating the middle Array
We have to keep 3 non-overlapping subarrays, right? So, the best way to ensure that they do not overlap is that we start by keeping the left array at the extreme left and the right subarray at the extreme right as shown in the figure below:
Obviously, this might not be the maximum sum subarray at the left or at the right. We are just looking for a point from where we can start and the arrays do not overlap.
Now, think and give the answer to this question. What are all the valid positions where we can keep the middle array?
In the array above, the valid positions will be from index 3 to index 7. Why till index 7? Because if we keep an array at index 8, it is of size 3 and the element arr[10] will be overlapped in the middle and right array. So, we can conclude the general formula from above i.e. the middle array can be placed from index K till index n-2K both K and n-2K inclusive.
How to find the Maximum Sum?
Now that we have studied the valid positions of all the three subarrays, let us now do the main task of finding the three maximum sum subarrays. Let us understand the general idea first:
So, the way to find the maximum sum subarrays is that first we calculate the sum of the middle array elements and then add the maximum subarray sum that lies on the left of this middle array and add the maximum subarray sum that lies on the right of this subarray. These two values are already present in the two dp arrays that we created.
So, let us start applying this procedure to the example that we have taken along from the beginning.
We will start from index 3. The left max subarray and the right max subarray sum along with the total maximum subarray sum is shown below:
So, as you can see, we have calculated the largest subarray sum so far considering the first combination of left, middle and right subarrays. Now, we can continue this procedure further and always compare the max sum obtained with the previous value of max sum. So, let us go to index 4 now.
Now, the sum that we have found is less than the previous value of sum. So, we will not update the value of the sum and it will be 31 only. So, dear reader, we can continue this procedure and we will get the value of the maximum sum. We recommend you complete this procedure for the remaining array on your own.
Also, refer to the solution video to understand the above procedure and clear all your doubts regarding it if any.
Now, let us see how we will get the lexicographically smallest order to print as the solution.
Lexicographically Smallest Order
We will take a variable and keep it at the starting point of the middle array. We will update that variable to the starting point of the next middle array only if the max sum value becomes greater than the previous. After this procedure, we will get the starting index of the middle array.
So, we have solved one problem. Now, how will we get the starting index of the left array and that too, lexicographically smallest one?
Well, if we know the starting index of the middle array, we already know the max subarray sum at its left i.e. dp1[i-1]. So, if we find out the first occurrence of the value dp1[i-1] in the dp1 array, it will give us the left subarray with the maximum sum and also, the lexicographically smallest index.
Similarly, if we calculate the first occurrence of dp2[i+k] from i+k-1 to n, we will get the lexicographically smallest index of the maximum sum subarray at the right.
We recommend you refer to the solution video () to understand the above point. So, we have now solved every problem. We have already discussed the method to find the maximum subarray sum for 3 non-overlapping arrays and we have now discussed the method to find the lexicographically smallest order.
We recommend you watch the complete solution video once to understand the video and the code given below too.
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 k = scn.nextInt();
solution(arr,k);
}
public static void solution(int[] arr, int k){
if(arr == null || arr.length < 3){
return;
}
int n = arr.length;
int[] left = new int[n];
int[] right = new int[n];
int[] third = new int[n];
int lsum = 0;
for(int i = 0; i < k; i++){
lsum += arr[i];
if(i == k - 1){
left[i] = lsum;
}
}
int prev = arr[0];
for(int i = k; i < n; i++){
lsum += arr[i];
left[i] = Math.max(left[i - 1], lsum - prev);
prev += arr[i - k + 1];
}
int rsum = 0;
for(int i = n - 1; i >= n - k; i--){
rsum += arr[i];
if(i == n - k){
right[i] = rsum;
}
}
prev = arr[n - 1];
for(int i = n - k - 1; i >= 0; i--){
rsum += arr[i];
right[i] = Math.max(right[i + 1], rsum - prev);
prev += arr[i + k - 1];
}
rsum = 0;
for(int i = n - 1; i >= n - k; i--){
rsum += arr[i];
if(i == n - k){
third[i] = rsum;
}
}
prev = arr[n - 1];
for(int i = n - k - 1; i >= 0; i--){
rsum += arr[i];
third[i] = rsum - prev;
prev += arr[i + k - 1];
}
int ans = 0;
int[] res = new int[3];
for(int i = k, j = 1; i <= n - (2*k); i++){
if(left[i - 1] + third[i] + right[i + k] > ans){
ans = left[i - 1] + third[i] + right[i + k];
res[0] = i - k;
res[1] = i;
res[2] = i + k;
}
}
int val = left[res[0] + k - 1];
for(int i = 0; i <= res[0] + k - 1; i++){
if(left[i] == val){
res[0] = i - k + 1;
break;
}
}
val = right[res[2]];
for(int i = res[2]; i <= n; i++){
if(third[i] == val){
res[2] = i;
break;
}
}
System.out.print(ans + " ");
for(int a : res){
System.out.print(a + " ");
}
}
}
java;
true";
Now that we have discussed everything, let us now analyze the time and space complexity of the above code.
Analysis:
Time Complexity :
{O(n) because we have first traversed the two matrices to fill them and later for calculating max sum subarray of 3 non overlapping arrays.
Space Complexity :
O(n) as we have made 2 dp arrays for solving this problem of size n.
We again recommend you watch the complete solution video once to understand everything in depth. With this, we have completed this problem.
