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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
