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!=kn)
{
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<nk;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<nk;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 ?
more clear than the editorialist’s explanation tbh 
,
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
Superb explanation! From the ground up.
1 Like
please provide more clear editorials
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;
}
}
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.
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.
But a null subarray is also a subarray so shouldn’t the answer be just 0 for that case. Just asking
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.