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.
