@ mohit my first post on here. this solution got ac in spoj
main()
{
unsigned int n,m,sum,max,i,j;
sum=0;max=1;
n=in.ReadNextUInt();
m=in.ReadNextUInt();
unsigned int *a = new unsigned int[n];
unsigned int *p = a;
for (i=0; i < n; i++)
*(p++) = in.ReadNextUInt();
i=0;
j=0;
while(j<n)
{
sum+=a[j++];
while(sum>m)
{
sum-=a[i++];
}
if(sum>max)
max=sum;
}
out.WriteUInt(max,'\n');
out.Flush();
return 0;
}
On 11/28/11, Mohit kumar lal <[email protected]> wrote:
> Given a array of positive integers ,You have to find the largest sum
> possible from consecutive sub-array but sum should be less than or equal to
> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> ans->12, sub-array={3,4,5}
>
> Firstly i tried with brute-force and then i also tried to solve it by DP
> but complexity were same ( O(n^2)) ....so plz try to provide a solution for
> O(nlgn) or O(n).
>
> --
> Mohit kumar lal
>
> IIIT ALLAHABAD
>
> --
> 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.
