There is my O(N) complex solution, where N is the length of the given array a[1...N].
Step1. sum[0] = 0, minima_index = 0, left = 0, right = 0, k = 1. Step2. sum[k] = sum[k - 1] + a[k]. Step3. If (sum[k] < sum[minima_index]) then minima_index = k. Step4. If (sum[k] - sum[minima_index] > sum[right] - sum[left]) then right = k, left = minima_index. Step5. k = k + 1, return to Step2 until k > N. Step6. subarray a[left...right] is the result, if (left == right == 0) then we should pick up zero integer numbers because all the numbers in array a[1...N] are negative. 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]. > 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.
