https://www.spoj.pl/problems/MAXSUMSQ/
Hi in above problem , i am getting TLE but according to given contraints ,
i think my code is good enough to run. Can any body help me here
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <climits>
#define VI vector <int>
typedef long long int LL;
using namespace std;
VI v;
LL x,nos;
//finding maximum sum subsequence
LL findx()
{
int sz=v.size();
LL maxsum=INT_MIN;
int maxstart=0,maxend=0;
LL currentsum=0;
int currentstart=0,currentend=0;
for(currentend=0;currentend<sz;currentend++)
{
currentsum=currentsum+v[currentend];
if(currentsum>maxsum)
{
maxsum=currentsum;
maxstart=currentstart;
maxend=currentend;
}
if(currentsum<0)
{
currentstart=currentend+1;
currentsum=0;
}
}
return maxsum;
}
// main Program
int main()
{
// freopen("input.txt","r",stdin);
int test;
int num;
map <LL , LL> m;
cin>>test;
LL sum=0;
int n;
int i;
while(test--)
{
sum=0;
nos=0;
m.clear();
m[0]=1;
scanf("%d",&n);
v.resize(n);
for(i=0;i<n;i++)
{
scanf("%d",&v[i]);
}
x=findx();
nos=0;
for(i=0;i<n;i++)
{
sum=sum+v[i];
nos=nos+m[sum-x];
m[sum]++;
}
cout<<x<<" "<<nos<<endl;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
