KCON - Editorial

editorial
, , , ,
21

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

22

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

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

23

more good for,
1
3 3
7 -8 4

24

Superb explanation! From the ground up.

1 Like
25

please provide more clear editorials

26

What’s wrong in my code ?? i am using kadena’s algo .
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lli long long int
#include
using namespace std;
lli maxsubarraysum(vectorarr,lli n)
{
int max_end_h=0;
int max_so_far=INT_MIN;
for(int i=0;i<n;i++)
{
max_end_h+=arr[i];
if(max_end_h<arr[i])
max_end_h=arr[i];
if(max_so_far<max_end_h)
max_so_far=max_end_h;
}
return max_so_far;
}
int main()
{
lli t;
cin>>t;
while(t–)
{
lli n,k;
cin>>n>>k;
vectorarr,brr;
for(lli i=0;i<n;i++)
{
lli x;
cin>>x;
arr.push_back(x);
}
for(lli i=0;i<k;i++)
{
for(lli j=0;j<n;j++)
brr.push_back(arr[j]);
}
lli maxval=maxsubarraysum(brr,n*k);
cout<<maxval<<endl;
}
}

27

Assume a case in which all the elements of array A are negative then you will get the ans as negative even in the case of max_sum_subarrray but if have initialised the best sum as zero then the answer you will get will be zero instead of negative.
If I am wrong please correct me too.

28

Keep adding the values until a non negative value is not encountered.
If its done from left to right, it will be your prefix.
If its done from right to left, it will be your suffix.

30

But a null subarray is also a subarray so shouldn’t the answer be just 0 for that case. Just asking

31

Why is it necessary to initialize prefixsum and suffixsum to INT_MIN. Initializing them to 0 should work just fine since even if they’re negative we’re not going to include them into the answer which is as good as declaring them 0 but the latter initialization gives WA whereas INT_MIN works.