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