Welcome back, dear reader. So, how is it going? In this article, we solve a very interesting problem called K CONCATENATION. So, what does this problem say?
Important Links : Problem Link, Solution Video
Prev Next
K Concatenation
You should name a variable using the same care with which you name a first-born child.
K Concatenation
Understanding the Problem:
We are given an array arr1. We are also given an integer k. The array, arr2, is formed by concatenating K copies of arr1. For instance if arr1 is {1,2} and k=3, then arr2={1,2,1,2,1,2}. We have to find the largest subarray sum in this arr2. We recommend you refer to the K CONCATENATION VIDEO once to understand the question completely.
We recommend you try to solve this problem on your own first and then refer to the solution to build your problem-solving skills and concepts.
Approach:
Time Complexity: O(n)
Space Complexity: O(1)
Explanation:
Dear reader, we recommend you refer to the KADANE'S ALGORITHM VIDEO first as it forms the basis for this problem and we are not going to discuss it here.
We hope that you have understood the question well. Let us start by taking an abstract example i.e. let us not consider any values for the arr1 now. Let us say that arr1 is {a,b,c,d,e,f} and it will be concatenated K times.
If K=1
If k=1, this means that we only have the array, arr1, as the array in which we have to find the largest/maximum subarray sum. So, this can be done very easily using Kadane's Algorithm that we have already studied. So, this is a very simple case.
If K>1
If k>1, this means that the array in which we have to find the largest subarray sum is a larger array than the arr1 we took. Two possible situations may arise here. Let us discuss both of them.
If Sum of the Array is Negative
We have the given array arr1 = {a,b,c,d,e,f}. This is just an abstract example. In reality, we will have an array of integer values. So, if the sum of this array is negative then the largest subarray sum of K such concatenated arrays can never be of the form:
What do we mean by this? If the sum of elements of the given array is negative, then the largest subarray sum of the same array concatenated K times can never be of such a subarray that starts from the first subarray and reaches the last subarray.
Let us prove this by the method of contradiction. Let us say that the largest subarray sum of the given K concatenated arrays is the sum as shown above.
Now, this sum has elements d, e, and f from the first array and the elements a, b from the last array. All the remaining elements of the rest k-2 arrays are also a part of this subarray sum.
So, the total sum will be :
Now, look at the first term of this sum. This can be generated if the subarray is taken from the first two arrays also as shown in the figure below:
Also, we can say that :
So, we have contradicted our own statement that the largest subarray sum will be (d+ e + f + a + b) + (k-2) x sum. Hence, by the method of contradiction, we can say that the largest subarray sum of K concatenated arrays (when the sum of the array is negative) will never be of the form as shown in img-1.
You may try to prove this with real integer values and some value of K as well. The conclusion that we can come up with is simple.
If the sum of the array is negative, find the largest subarray sum in the first two arrays only using Kadane's Algorithm.
The largest subarray sum will be in the first two arrays, this is certain, but, it can also be of two forms as shown in the examples below:
So, if the sum of the array is negative, the largest subarray sum will either be in the first array only or in between the first two arrays and not more than that.
So, we can say that if k>=2, and the sum of the array is negative, the largest subarray sum can be found by applying Kadane's Algorithm in 2 concatenated arrays.
Now, let us see what happens if the sum is positive.
If the sum of Array is Positive
If the sum of the array is positive, the largest subarray sum will always be of the form as shown in img-1 i.e. starting from the first array and reaching the last array.
We can prove this too by the method of contradiction.
Let us say we assume the following marked elements to be the largest subarray sum.
So, the largest subarray sum according to us right now is (d + e + f + a + b). To contradict ourselves, let us consider another case as shown below:
So, the sum of the above subarray that we have considered will be :
If we think carefully, this sum will always be greater than the subarray sum taken by considering just 2 arrays. This is because the sum of the complete array is positive.
Therefore, we have contradicted our own statement. Hence, the largest subarray sum will not be just among the first two arrays. But, how do we prove that it will be the sum of a subarray starting from the first array and reaching the last array?
See, the differentiating factor between these two subarray sums (that we have considered above) is that the second sum has the sum of arrays added to it. Now, this will be maximum if all the arrays in between are added to the sum.
So, the only way to maximize the subarray sum is that we should include all the arrays in between.
So, the largest subarray sum of K concatenated arrays when the sum of the array is greater than 0 is always of the form starting from the first subarray and reaching the last subarray.
Now, if we consider traversing all the arrays in between, that will be a lot of work to do. Rather, we have already generated the formula to do so (img-8).
So, if the sum of an array is greater than zero, the largest subarray sum will be the largest subarray sum of 2 concatenated arrays + (k-2) multiplied by the sum of one array. Why? Think about this!!!!
We have finally reached the following conclusions:
- If K=1, apply Kadane's Algorithm on one array only and get the answer.
- If K>1 and the sum of one array is less than zero, apply Kadane's Algorithm on the 2 concatenated arrays and get the answer.
- If K>1 and the sum of one array is positive, apply Kadane's Algorithm on 2 concatenated arrays and add (k-2) x sum of one array into it.
So, dear reader, we hope that you have understood the complete analysis that we have done above. We recommend you refer to the solution video to understand the complete analysis that we have discussed above and clear your doubts regarding it if any.
Now that we have understood the process completely, let us write the code for the same:
import java.io.*;
import java.util.*;
public class Main {
public static int kadanes(int[] arr)
{
int csum=arr[0];
int msum=arr[0];
for(int i=1;i< arr.length;i++)
{
if(csum>=0)
{
csum=csum+arr[i];
}
else
{
csum=arr[i];
}
if(csum>msum)
{
msum=csum;
}
}
return msum;
}
public static int kadanesoftwo(int[] arr)
{
int[] narr=new int[arr.length*2];
for(int i=0;i< arr.length;i++)
{
narr[i]=arr[i];
}
for(int i=0;i< arr.length;i++)
{
narr[i + arr.length]=arr[i];
}
return kadanes(narr);
}
public static long solution(int[] arr, int k, long sum) {
// write your code here
if(k==1)
{
return kadanes(arr);
}
if(sum<0)
{
return kadanesoftwo(arr);
}
return kadanesoftwo(arr) + (k-2)*sum;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
long sum = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = scn.nextInt();
sum += arr[i];
}
int k = scn.nextInt();
System.out.println(solution(arr, k, sum));
}
}
java;
true";
The above code is written and explained in the solution video. You may refer to it to clear all your doubts regarding the code if any. Let us now analyze the time and space complexity of this code.
Analysis
Time Complexity:
The time complexity of this code is O(n) as we are applying Kadane's Algorithm to a maximum of 2n elements i.e. 2 concatenated arrays. We know that Kadane's Algorithm finds the largest subarray sum in O(n) time. So, the time complexity becomes O(n).
Space Complexity:
We have not used any extra space. Hence the space complexity is O(1).
So, dear reader, we hope that you have understood the above solution. We recommend you refer to the complete solution video once as it will build your concepts really strong. With this, we have completed this problem.
Suggestions:
Here are a few suggestions from our side that you don't want to miss:
- See, this question was more about analyzing the different cases rather than the coding part. This can happen in a lot of further questions. So, it is very important that you at least remember the algorithms like Kadane's algorithm so well that you don't even have to waste a second thinking about them so that you can focus completely on the main concept of the question.
- We recommend you refer to the solution video for every question once, even if you have solved the problem yourself as it is going to give you some great insights, and also you have good chances of learning something new that you don't know already. So, keep practicing and working hard. Till then, Happy Coding!!!
