@ashita
I think its working fine for this seq also
i=1 and j=5
and sum =25
{3,4,17,-8,9}correct me On Sat, Sep 11, 2010 at 2:16 AM, ashita dadlani <ash....@gmail.com> wrote: > 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 <ash....@gmail.com> 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 <ash....@gmail.com>wrote: >> >>> @ashish: >>> what if the array is {-2,3,4,17,-8,9}? >>> >>> >>> On Wed, Sep 8, 2010 at 8:52 AM, Anand <anandut2...@gmail.com> wrote: >>> >>>> Maximum Value Contiguous Subsequence problem in O(n). >>>> http://codepad.org/BhYxSlp4 >>>> >>>> >>>> On Tue, Sep 7, 2010 at 2:40 PM, ashish agarwal < >>>> ashish.cooldude...@gmail.com> wrote: >>>> >>>>> yeah..it will be i=j+1; >>>>> it was misprinted >>>>> >>>>> >>>>> On Tue, Sep 7, 2010 at 10:57 AM, Sahana Gururaj <sahan...@gmail.com>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 < >>>>>> ashish.cooldude...@gmail.com> 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 <shashank7andr...@gmail.com>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 algoge...@googlegroups.com. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>>>>>> To unsubscribe from this group, send email to >>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>> . >>>>>>> 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 algoge...@googlegroups.com. >>>>>> To unsubscribe from this group, send email to >>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
