@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.
