I have used kadane algorithm to solve this Chef to Chef question but getting wrong answer,can anyone explain why kadane algo is not applicable here.
This is my code:
#include<bits/stdc++.h>
using namespace std;
//ASCII range for lowercase => 97 to 122
//ASCII range for uppercase => 65 to 90
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define M 1000000007
typedef long long int lli;
#define pb push_back
#define tc lli t;cin >> t;while(t–)
#define ffi(x,y) for(lli i=x;i<y;i++)
#define ffj(x,y) for(lli j=x;j<y;j++)
#define frj(x,y) for(lli j=x;j>y;j–)
#define fri(x,y) for(lli i=x;i>y;i–)
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899863;
pair<lli,lli> kthmaxminArray(vector a,lli n,lli k)
{
sort(a.begin(),a.end());
lli kth_mn=a[k-1],kth_mx=a[n-k];
pair<lli,lli> p;
p = make_pair(kth_mn,kth_mx);
return p;
}
int kadane(vector a,lli n)
{
vector aa;
lli max_so_far = LLONG_MIN, max_ending_here = 0,start =0, end = 0, s=0;
ffi(0,n)
{
max_ending_here += a[i];
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0)
{
max_ending_here = 0;
s = i + 1;
}
}
ffi(start,end+1)
{
aa.push_back(a[i]);
}
sort(aa.begin(),aa.end());
lli p1 = aa[aa.size()-1];
lli p2 = aa[aa.size()-2];
return max_so_far-(p1+p2);
}
bool isPowerof2(int x)
{
return (x && (!(x & (x - 1))));
}
lli fast_gcd(lli a,lli b)
{
if(b==0)
return a;
else
return fast_gcd(b, a % b);
}
lli fast_power(lli b, lli n)
{
if(n==0)
return 1;
if(n==1)
return b;
long long halfn=fast_power(b,n/2);
if(n%2==0)
return ( halfn * halfn ) % M;
else
return (((halfn*halfn)% M)b)%M;
}
bool ispalindrome(string str,lli l,lli r)
{
while(l<=r)
{
if(str[l]!=str[r])
return false;
l++;
r–;
}
return true;
}
lli reversenum(lli n)
{
lli ans=0;
while(n)
{
ans= (ans10)+n%10;
n/=10;
}
return ans;
}
//function returning a pointer
lli * reverseArray(lli a[],lli n)
{
int head=0,tail=n-1;
while(head<tail)
{
swap(a[head],a[tail]);
head++;
tail–;
}
return a;
}
pair<lli,lli> maxminArray(lli a[],lli n)
{
lli mn=LLONG_MAX,mx=LLONG_MIN;
pair<lli,lli> p;
ffi(0,n)
{
if(mn>a[i])
{
mn = a[i];
}
}
ffi(0,n)
{
if(mx<a[i])
{
mx = a[i];
}
}
p = make_pair(mn,mx);
return p;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
tc
{
lli n;
cin>>n;
vector a(n);
ffi(0,n)
{
cin>>a[i];
}
cout<<kadane(a,n)<<’\n’;
}
return 0;
}