Comments by Member 12552651

Member 12552651 19-Jun-16 8:09am View

I have already mentioned the contest is over already a week ago.Now its quite legal to know the answer,sir.I have already qualified for elimination round and yeah i know how to code.Just needed your help in this question to prepare for further rounds.Thnx

Member 12552651 30-May-16 21:29pm View

Will it be effiecient? I think its still 0(n^2).

Member 12552651 30-May-16 21:24pm View

I have tried to skip only negative numbers.Thecomplexity is better than 0(n^2) but still getting TLE.Any help

Member 12552651 30-May-16 6:32am View

Can it be more effiecient. I mean to find sum by skipping one element in above question.getting TLE with above aproach.Input size is upto 10^5 and above mentioned is a O(n^2) approach.

Member 12552651 29-May-16 7:16am View

can you help me out?

Member 12552651 29-May-16 7:15am View

nothing like that

Member 12552651 29-May-16 7:13am View

quesion.i guess

Member 12552651 29-May-16 7:10am View

which one?

Member 12552651 29-May-16 6:44am View

Done.Now help me out

Member 12552651 29-May-16 6:02am View

Done

Member 12552651 29-May-16 5:32am View

Its not a homework.I just required an algorithm.I can do the rest job.Thank You

Member 12552651 29-May-16 5:29am View

first i have searched out for the maxstartIndex as well as maxEndIndex as per Kadane's algo.Then the manipulation is based on if maxStartIndex and maxEndIndex are same or not

Member 12552651 29-May-16 5:27am View

Deleted

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
int t;
long int temp;
cin>>t;
while(t>0)
{
long long int n;
cin>>n;
long long int a[n];
for(int i=0;i<n;i++){cin>>a[i];}
long long int maxStartIndex=0;
long long int maxEndIndex=0;
long long int maxSum=a[0];
for(int i=0;i<n;i++)
{
="" if(maxsum="">a[i])
{
maxSum=a[i];
}
}
long long int cumulativeSum= 0;
long int maxStartIndexUntilNow=0;

for (int currentIndex = 0; currentIndex < n;currentIndex++) {

long long int eachArrayItem = a[currentIndex];

cumulativeSum+=eachArrayItem;

if(cumulativeSum>maxSum){
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
if(maxStartIndex==maxEndIndex)
{
long long int xyz;
if((maxEndIndex + 2)<=n-1 && a[maxEndIndex+1]<0 )
{
int i=2;
xyz=maxSum;
for(int i=maxEndIndex+2;i<=n-1;i++)
{
if(a[i]<0){break;}
maxSum=maxSum+ a[i];
}
temp=maxSum;
}
if((maxStartIndex-2)>=0 && a[maxStartIndex-1]<0 )
{
maxSum=xyz;
int i=2;
while(a[maxStartIndex-i]>0 && i>=0)
{
maxSum=maxSum + a[maxStartIndex-i];
i--;
}
cout<<maxSum<<"\n";

if(temp>maxSum)
{
maxSum=temp;
}
}
}
else
{
long long int min=a[maxStartIndex];
for(int i=maxStartIndex;i<=maxEndIndex;i++)
{
if(min>a[i]){min=a[i];}
}
if(min<0)
{
maxSum=maxSum + (-min);
}
else
{
int flag=0;
if((maxEndIndex + 2)<=n-1 && a[maxEndIndex+1]<0 && a[maxEndIndex+2]>0)
{maxSum=maxSum + a[maxEndIndex+2];temp=maxSum;flag=1;}
if((maxStartIndex-2)>=0 && a[maxStartIndex-1]<0 && a[maxStartIndex-2]>0)
{
if(flag==1){maxSum=maxSum - a[maxEndIndex+2];}
maxSum=maxSum + a[maxStartIndex-2];
if(temp>maxSum)
{
maxSum=temp;
}
}
}
}
cout<<maxSum<<"\n";
t--;
}
return 0;
}

Comments by Member 12552651 (Top 13 by date)