crude C# O(n) soln... Haven't read the entire post... u probably already have the answer
private string MaxSubarray(string p) { var array = p.Split(','); int currentmax = -1,maxstart = -1, maxend = -1; int firstpositveindex = -1, arraysize = array.Length; int thissum = 0; for(int i=0; i< arraysize; i++) { var thisnumber = Int32.Parse(array[i].Trim()); if (thisnumber < 0 && firstpositveindex == -1) continue; if(firstpositveindex ==-1) firstpositveindex = i; if (0 >= (thisnumber + thissum)) { firstpositveindex = -1; thissum = 0; continue; } else thissum = thisnumber + thissum; if (thissum > currentmax) { currentmax = thissum; maxstart = firstpositveindex; maxend = i; } } string result = string.Empty; if (currentmax >= 0 && maxstart >= 0 && maxend >= 0) { for (int i = maxstart; i <= maxend; i++) { result = result + array[i] + ","; } result += "MAX=" + currentmax; } return result; } On Sep 6, 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.