KCON - Editorial

@nikmul19

      Your problem is to find the maximum sub array of B. Maximum SubArray of an array A is a continuous SubArray within the array A that has the largest Sum. For e.g.. In a array having elements {-25 , 20, -3, -16, -23, 18, 20, -7, 12, -5, -22} (Index starts with 0) the Maximum SubArray is from index 5 to index 8 which has a sum of 43. No other continuous SubArray within A would have sum which exceeds 43. The best method for finding Maximum SubArray is [Kadanae's algorithm][1].

     Okay now let's jump into the problem. Here you have to find the Maximum SubArray for an array B which is a k-times repetitive array of A. For e.g.. if A is {3, 2, -1} and K is 3 then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. 

     First method: 
            You can create a  array B using A and you can deploy Kadanae's algorithm on it to find the maximum SubArray. But it's not a good solution. Array A can have upto 10^5 elements and K can also have value upto 10^5. So the size of the array B will be very large and it's a waste of memory to create an array B.

    Optimised Method:
            The maximum SubArray of B can be the sum of all its elements. For e.g.. if A is {3, 2, -1} and K is 3, then B will be {3, 2, -1, 3, 2, -1, 3, 2, -1}. The sum of all the elements in B will give us 12. To find this one we don't need to create the array B. We can simply find the sum of all the elements in array A and we can mutilply it with K. i.e (sum of elements in A)*k, Since B is the k-time repetition of the array A. Okay now we found out that the maximum SubArray of B is 12. 
           Oh Wait Wait we have just made that one wrong. Look at the array B carefully, we can omit the last term in it so that the sum will become 13. For this one The author uses prefix and suffix calculations. You can clearly understand with this example. Now array A is {-1, -2, 8, 9, 10, -2, -1} and consider K is 10. A is repeated 10 times in B. Consider the first repetition of A is A1, second is A2 and so on. So now our B array will be {A1, A2, A3, A4, A5, A6, A7, A8, A9, A10}. By finding only the (sum of elements in A)*k you will get the answer 270. But if you omit the first two elements in A1 and the last two elements in A10, You will get the Maximum SubArray as 276. So here we can check whether it is possible to omit some initial elements in A1 and some Final elements in A10. So the author is using prefix and suffix variables for that to calculate the sum of A1 and A10 specifically and he adds the remaining elements i.e answer = {prefix + SOE(A2) + SOE(A3) + SOE(A4) + SOE(A5) + SOE(A6) + SOE(A7) + SOE(A8) + SOE(A9) + suffix} , which in simplified form becomes {prefix + SOE(A)*(k-2) + suffix}. This is what he does. 
         SOE - Sum Of Elements. If SOE is positive then do this above calculation. Else just add the prefix and suffix.

if(SOE(A) > 0)

{

answer = {prefix + SOE(A)*(k-2) + suffix}.

}

else

{

answer = {prefix + suffix}.

}

       Now consider this test case. consider A as {12, -200, 12} and K is 3. Now the total sum becomes -ve. Look at B {12, -200, 12, 12, -200, 12, 12, -200, 12} i.e {A1, A2, A3}. Here the prefix will be 12 and suffix will also be 12. so the answer will be 24 which is the sum that exists at indexes 2 and 3, and indexes 5 and 6.
51 Likes

how to calculate prefix and suffix
and also what they mean

4 Likes

Thanks @pazhamalai

Author’s solution is giving access denied

3 Likes

what about when all numbers are zero consider -3 -1 -2 and k = 3
in this case what will be suffix and prefix? And according to the @pazhamalai explanation what should be the answer?

1 Like

Try this test case
1
3 2
7 -8 4

1 Like

Excellent explanation dde

2 Likes

It can be solved using Arithmetic Progression…
Just Find the value of Array A for K=1 , K=2, K=3 and see the pattern…
let’s say for k=1 answer is X1
for k=2 answer is X2
for k=3 answer is X3
if k==1 print X1
if k==2 print X2
if k>2 print x2+(k-2)*(x3-x2)

4 Likes

#include
using namespace std;
#define ll long long int
int kadane(ll k[],ll n)
{ ll i,sum=0,ma=-25;
for(i=0;i<n;i++)
{
sum+=k[i];
if(sum>ma)
ma=sum;
if(sum<0)
sum=0;
}
return ma;
}
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n,k,i,j,c=0;
cin>>n>>k;
ll a=new ll[n];
ll b=new ll [nk];
for(i=0;i<n;i++)
cin>>a[i];
while(c!=k
n)
{
for(j=0;j<n;j++)
{
b[c++]=a[j];
}
j=0;
}
ll sum=kadane(b,n*k);
cout<<sum<<endl;
}
return 0;
}
this is giving a WA

1 Like

Great explanation. Thanks for writing this .

1 Like

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–) {
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) {
cin>>a[i];
}
int b[nk];
for(int i=0;i<n
k;i++) {
b[i]=a[i%n];
}
int flag=0;
for(int i=0;i<nk;i++) {
if(b[i]>=0) {
flag=1;
break;
}
}
if(flag==1) {
long long int current_sum=0;
long long int best_sum=0;
for(int i=0;i<n
k;i++) {
current_sum+=b[i];
if(best_sum<current_sum)
best_sum=current_sum;
if(current_sum<0)
current_sum=0;
}
cout<<best_sum<<endl;
}
else {
int max=b[0];
for(int i=1;i<n*k;i++) {
if(b[i]>max)
max=b[i];
}
cout<<max;
}
}
return 0;
}

above code should atleast pass the testcases for subtask A but getting WA. also getting SIGSSEGV error for test cases in subtask B.

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–) {
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) {
cin>>a[i];
}
int b[n k];
for(int i=0;i<n
k;i++) {
b[i]=a[i%n];
}
int flag=0;
for(int i=0;i<n k;i++) {
if(b[i]>=0) {
flag=1;
break;
}
}
if(flag==1) {
long long int current_sum=0;
long long int best_sum=0;
for(int i=0;i<n
k;i++) {
current_sum+=b[i];
if(best_sum<current_sum)
best_sum=current_sum;
if(current_sum<0)
current_sum=0;
}
cout<<best_sum<<endl;
}
else {
int max=b[0];
for(int i=1;i<n*k;i++) {
if(b[i]>max)
max=b[i];
}
cout<<max;
}
}
return 0;
}

above code should atleast pass the testcases for subtask A but getting WA. also getting SIGSSEGV error for test cases in subtask B.

I got WA when I intitialised the max-sum (used for kadane’s algo) to zero and AC when i intialized it to LONG_MIN . I can’t figure why it’s happening as even if there are only negative elements in array the max-sum is zero by default (by taking none of the element). Please correct me.

Can anyone explain, why we decide to return ans with respect to the sum of the array A and not max_subarray_sum of array A ?

@melfice @hruday968

Question is great, but explanation is poor. Try to work on it. :metal:

1 Like

Nice Explanation @pazhamalai ! Well done.
We need people like you to be honest.

1 Like

more clear than the editorialist’s explanation tbh :slightly_smiling_face:,

1 Like

can someone pls explain why have we made 2A array in this question and how have we arrived at the logic?

https://www.codechef.com/viewsolution/38153405

Please help me figure out the mistake in the code.
Thanks in advance.

more good for,
1
3 3
7 -8 4