i used the following code..
getting wa
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits.h>
#include<map>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,sm=0;
scanf("%d",&n);
vector<int> v(n);
map<int,int> mp;
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
int sum=INT_MIN,cur=0;
for(int i=0;i<n;i++)
{
cur+=v[i];
mp[cur]++;
if(cur>sum)
{
sum=cur;
}
if(cur<0)
cur=0;
}
//cout<<sum<<"\t"<<mp[sum]+mp[0]<<"\n";
printf("%d %d\n",sum,mp[sum]+mp[0]);
}
}
On Mon, Mar 14, 2011 at 7:41 PM, tech rascal <[email protected]>wrote:
> @ankur: can u plz xplain ur approach??
>
>
> On Sun, Mar 13, 2011 at 12:26 PM, Ankur Khurana
> <[email protected]>wrote:
>
>> 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.
>>
>
> --
> 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.
>
--
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.
