http://codepad.org/Jui20xme <http://codepad.org/Jui20xme>a little modification over anand's code.
On Sat, Sep 11, 2010 at 2:33 PM, ashita dadlani <[email protected]> wrote: > @anand: > the maximum sum obtained from your solution is correct. > However,the subarray printed is not correct for the following case: > {-2,3,4,17,-8} > -8 is also getting printed which is not a part of thw subsequence. > > > On Sat, Sep 11, 2010 at 2:00 PM, ashita dadlani <[email protected]> wrote: > >> @ashish: >> what if the array is {-2,3,4,17,-8,9}? >> >> >> On Wed, Sep 8, 2010 at 8:52 AM, Anand <[email protected]> wrote: >> >>> Maximum Value Contiguous Subsequence problem in O(n). >>> http://codepad.org/BhYxSlp4 >>> >>> >>> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal < >>> [email protected]> wrote: >>> >>>> yeah..it will be i=j+1; >>>> it was misprinted >>>> >>>> >>>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj <[email protected]>wrote: >>>> >>>>> In the else if condition, the increment of the end index i should be >>>>> i=j+1, not i=j+i; Otherwise the algo is right, follows the principles of >>>>> Kadane's algo : >>>>> http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm >>>>> >>>>> On Mon, Sep 6, 2010 at 3:50 PM, ashish agarwal < >>>>> [email protected]> wrote: >>>>> >>>>>> int max=0,sum=0,begin=0,end=0,i=0; >>>>>> for(int j=0 to n){ >>>>>> sum+=a[j]; >>>>>> if(max<sum){ >>>>>> max=sum; >>>>>> begin=i; >>>>>> end=j; >>>>>> } >>>>>> else if(sum<0){ >>>>>> i=j+i; >>>>>> sum=0; >>>>>> } >>>>>> >>>>>> return sum; >>>>>> i will tell the starting index and j will tell ending index; >>>>>> o(n); >>>>>> correct me if i am wrong >>>>>> >>>>>> >>>>>> >>>>>> On Mon, Sep 6, 2010 at 1:42 PM, bittu <[email protected]>wrote: >>>>>> >>>>>>> Given a sequence of integers, find a continuous subsequence which >>>>>>> maximizes the sum of its elements, that is, the elements of no other >>>>>>> single subsequence add up to a value larger than this one. An empty >>>>>>> subsequence is considered to have the sum 0; thus if all elements are >>>>>>> negative, the result must be the empty sequence. >>>>>>> >>>>>>> >>>>>>> Solution:O(n^2) i want O(nlogn).......??????????????????? >>>>>>> >>>>>>> >>>>>>> >>>>>>> #include <stdio.h> >>>>>>> #include<conio.h> >>>>>>> #include<iostream.h> >>>>>>> #include<stdlib.h> >>>>>>> int main() >>>>>>> { >>>>>>> int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1}; >>>>>>> int length = 11; >>>>>>> >>>>>>> int begin, end, beginmax, endmax, maxsum, sum, i; >>>>>>> >>>>>>> sum = 0; >>>>>>> beginmax = 0; >>>>>>> endmax = -1; >>>>>>> maxsum = 0; >>>>>>> >>>>>>> >>>>>>> for (begin=0; begin<length; begin++) { >>>>>>> sum = 0; >>>>>>> for(end=begin; end<length; end++) { >>>>>>> sum += a[end]; >>>>>>> if(sum > maxsum) { >>>>>>> maxsum = sum; >>>>>>> beginmax = begin; >>>>>>> endmax = end; >>>>>>> } >>>>>>> >>>>>>> } >>>>>>> cout<<sum<<"\t"; >>>>>>> } >>>>>>> cout<<endl; >>>>>>> for(i=beginmax; i<=endmax; i++) { >>>>>>> printf("%d\n", a[i]); >>>>>>> } >>>>>>> >>>>>>> getch(); >>>>>>> } >>>>>>> >>>>>>> >>>>>>> its has time complexity O(n^2) ..does better solution exist >>>>>>> >>>>>>> -- >>>>>>> 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]<algogeeks%[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]<algogeeks%[email protected]> >>>>>> . >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Sahana Gururaj >>>>> >>>>> >>>>> -- >>>>> 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]<algogeeks%[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]<algogeeks%[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]<algogeeks%[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.
