This does not look like a solution for the posted problem.
This fails the test case {2, 7, 6, 0, 100}, where the answer should
have been 4, for k=0 and j=4.Manish On Mar 20, 1:49 pm, saurabh gupta <[email protected]> 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 <[email protected]> wrote: > > > On Mar 15, 10:07 am, saurabh gupta <[email protected]> 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 [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. > > -- > 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 [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.
