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 <[email protected]> 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 <[email protected]>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 <[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]> >> <algogeeks%[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]<algogeeks%[email protected]> >> . >> 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 [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.
