Hi all, How about this ? set K to the first element i.e Array[0] and set j to the last element i.e Array[size-1]. Decrement the index j until you find Array[j] > Array[j+1] and increment the index k until you find Array[k] < Array[k-1] and do this until you find the conditions met. Does it solve the original problem ?
Or is it the largest Non decreasing sequence thats been asked in original problem . On Wed, Mar 24, 2010 at 1:08 PM, saurabh gupta <sgup...@gmail.com> wrote: > Hi Achala, > > This fails for: > 0 1 2000 3 4 5 6 > > prog's output: > arr[j]=2000,arr[k]=0,j=2,k=0 > > correct output should be: > arr[j]=6,arr[k]=0,j=6,k=0 > > you seem to be relying on the difference in the 'values' (contents) instead > of the index span. > > On Mon, Mar 22, 2010 at 11:10 PM, achala sharma <3.ach...@gmail.com>wrote: > >> One Solution for Largest span in array,I have checked it on many >> inputs,according to me its working fine >> >> >> void Large_Span(int * arr,int num_elem) >> >> { >> >> int j=1,k=0,i,prev_k=0; >> >> for(i=1;i<num_elem;i++) >> >> { >> >> if(arr[i]>arr[i-1]) >> >> { >> >> if((arr[j]-arr[k])<(arr[i]-arr[i-1])) >> >> { >> >> if(j<arr[i] && k<=arr[i-1]) >> >> { >> >> j=i; >> >> } >> >> else if((j<arr[i] && k>arr[i-1])||(j>arr[i] && k>arr[i-1])) >> >> { >> >> j=i; >> >> k=i-1; >> >> } >> >> >> >> } >> >> else if(arr[k]>arr[i-1]) >> >> { >> >> if(k<j) >> >> { >> >> prev_k=k; >> >> k=i-1; >> >> } >> >> >> >> } >> >> else if(arr[j]<arr[i]) >> >> j=i; >> >> } >> >> else >> >> { >> >> if(arr[k]>arr[i]) >> >> { >> >> if(i>j) >> >> { >> >> prev_k=k; >> >> k=i; >> >> } >> >> else >> >> k=i; >> >> } >> >> } >> >> } >> >> if(k>j) >> >> { >> >> k=prev_k; >> >> } >> >> printf("arr[j]=%d,arr[k]=%d,j=%d,k=%d",arr[j],arr[k],j,k); >> >> } >> >> >> On Mon, Mar 22, 2010 at 8:28 AM, Manish <mannishmaheshw...@gmail.com>wrote: >> >>> 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 <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> >>> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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. >>> >>> >> -- >> 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. > -- 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.