Is the problem like this, Given an array of integers A[N], find the maximum value of (j-k) such that A[k] <= A[j] & j>k." *for all i >j and i<=k, A[i]<=A[i-1] " * On Sat, Mar 20, 2010 at 11:19 PM, saurabh gupta <sgup...@gmail.com> wrote:
> This may not be the optimal solution to > > " Given an array of integers A[N], find the maximum value of (j-k) such > that A[k] <= A[j] & j>k. > I am looking for a solution with time complexity better than O(N^2)." > > this was in response to > > "how u can solve it in o(n)" > and > > "how to solve this in the claimed O(N) time." > > > > > > On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland <rpbol...@gmail.com>wrote: > >> >> >> On Mar 15, 10:07 am, saurabh gupta <sgup...@gmail.com> wrote: >> > while you scan the array >> > maintain four indices plus two lengths >> > two indices and a length mark one sub-array - start,end, length >> > each such sub-array indicates a non-decreasing sequence, >> > call them S1 and S2. >> > >> > while one scans, S2 keeps track of incoming elements (curr sequence) >> > S1 keeps track of the maximum length (along with indices) so far (prev >> > sequence) >> > as one encounters an element which is less than the previous element, >> > this marks the end of S2, >> > S1 replaces S2 if len S2 > len S1 else S2 starts afresh from this new >> > element. >> > >> > In the end if len S2 > len S1 answer = S2 >> > else answer = S1. >> > >> > PS: In the beginning and till one encounters a smaller element than the >> > prev one for the first time, S1 = S2 >> > >> >> >> I agree that this is a nice algorthithm that solves the >> largest non decreasing sequence problem. >> However, I don't agree that this solves the problem >> originally posted. >> >> Regards, >> >> Ralph Boland >> >> -- >> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. > Says he feels all alone in a threatening world where what lies ahead is > vague and uncertain. Doctor says "Treatment is simple. Great clown > Pagliacci is in town tonight. Go and see him. That should pick you up." Man > bursts into tears. Says "But, doctor...I am Pagliacci." > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Vikrant Singh -- 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.
