@Shashank: Without looking over your algorithm in detail, let me just say that it solves a different problem than the one asked by the original poster. You are finding the kth maximum sum, but the problem asks to find all of the first n maximum sums. So you would have to apply your algorithm n times. The total complexity for the original problem would be O(n^2).
Dave On Sep 2, 5:18 am, WgpShashank <shashank7andr...@gmail.com> wrote: > Yes I Think Its Obviously O(N) Algorithm :P > > Here is Approach > > Algorithm: > Take 0th index value from 1st array & 1st index value from 2nd array store > it in S1 > Now 0th index value from 2nd array & 1st index value from 1st array , store > in S2 > Also stores starting & ending index of each array -take care-off > > initialize maxsum variable to a[0]+b[0] > Keep checking until we found kth sum from array a & b where a is from 1st & > b is from > if s1>s2 then increment array b lastindex until its equal to length of this > array & update maxsum=s1 > else then increment array a last-index until its equal to length of this > array > maxsum=s2; > > Finally Return maxsum; > > Here is More > infohttp://shashank7s.blogspot.com/2011/08/find-kth-largest-sumab-possibl... > > Thanks > Shashank Mani > Computer Science > Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
