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