Re: [algogeeks] SPoj maximum sum subseuence
Hey Ankur,
Why dont u just modify the findx function itself to return the frequency of
occurence of maxsum as well.
On Sun, Mar 13, 2011 at 12:26 PM, Ankur Khurana 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
> #include
> #include
> #include
> #include
> #include
> #include
> #include
> #include
> #define VI vector
> 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;
>
int freq=0;
> for(currentend=0;currentend {
> currentsum=currentsum+v[currentend];
>
>
if(currentsum==maxsum) {
freq++;
}
> if(currentsum>maxsum)
> {
> maxsum=currentsum;
> maxstart=currentstart;
> maxend=currentend;
>
freq=0;
> }
> if(currentsum<0)
> {
> currentstart=currentend+1;
> currentsum=0;
> }
> }
>
> return maxsum;
> }
>
>
> // main Program
> int main()
> {
> // freopen("input.txt","r",stdin);
> int test;
> int num;
> map 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 {
>scanf("%d",&v[i]);
> }
> x=findx();
> nos=0;
>
//Remove this for loop. No need.
> for(i=0;i {
> sum=sum+v[i];
> nos=nos+m[sum-x];
> m[sum]++;
> }
> cout< }
>
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
This shld help.
Cheers
Nikhil Jindal
https://sites.google.com/site/aboutnikhiljindal/
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] SPoj maximum sum subseuence
i used the following code..
getting wa
#include
#include
#include
#include
#include
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 v(n);
map mp;
for(int i=0;isum)
{
sum=cur;
}
if(cur<0)
cur=0;
}
//cout @ankur: can u plz xplain ur approach??
>
>
> On Sun, Mar 13, 2011 at 12:26 PM, Ankur Khurana
> 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
>> #include
>> #include
>> #include
>> #include
>> #include
>> #include
>> #include
>> #include
>> #define VI vector
>> 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> {
>> 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 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> {
>>scanf("%d",&v[i]);
>> }
>> x=findx();
>> nos=0;
>> for(i=0;i> {
>> sum=sum+v[i];
>> nos=nos+m[sum-x];
>> m[sum]++;
>> }
>> cout<> }
>>
>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] SPoj maximum sum subseuence
@ankur: can u plz xplain ur approach??
On Sun, Mar 13, 2011 at 12:26 PM, Ankur Khurana 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
> #include
> #include
> #include
> #include
> #include
> #include
> #include
> #include
> #define VI vector
> 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 {
> 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 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 {
>scanf("%d",&v[i]);
> }
> x=findx();
> nos=0;
> for(i=0;i {
> sum=sum+v[i];
> nos=nos+m[sum-x];
> m[sum]++;
> }
> cout< }
>
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SPoj maximum sum subseuence
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
#include
#include
#include
#include
#include
#include
#include
#include
#define VI vector
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;currentendmaxsum)
{
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 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;ihttp://groups.google.com/group/algogeeks?hl=en.
