last night i was going through a similar kind of question and tried to implement its algo in this question...If anyone finds any counter example for it, please do comment..
Algo:-
*Let the array be A[].
We can keep two arrays B[] and C[] which will do the following work..
B[i] will store the minimum value in A[] till ith index
C[i] will store the maximum value (starting from the end) in A[i] till ith
index.*
*Lets say taking amit's example...*
*A[] = { 5 3 4 5 3 3 }*
*then B[] = {5,3,3,3,3,3}; //starting from the beginning.
and C[] = {5,5,5,5,3,3}; //starting from the end*
*the we can take two pointers i and j and a max_diff (all initialised to 0)
and run the following loop*
*while(j<(sizeof(A)/sizeof(A[0])))
{
while(B[i]<C[j]) *
* j++;
if(max_diff<j-i-1)
max_diff = j-i-1;
i++;
j++;
}
the code for creating B[] and C[] can be as follows...
let N = (sizeof(A)/sizeof(A[0]))
B[0] = A[0];
for(i=1;i<N;i++)
{
B[i] = ((A[i]<B[i-1])?A[i]:B[i-1]);
}
C[N-1] = A[N-1];
for(i=N-2;i>=0;i--)
{
C[i] = ((A[i]>B[i+1])?A[i]:B[i+1]);
}*
For the given example, answer is coming to be j = 4,i=1,max_diff = 4-1-1 = 2
I hope I am clear... [?]
On Wed, May 18, 2011 at 4:52 PM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
> I think it can be done in O(n) but the auxilliary space required will be
> more... in the solution which i have got its in the order of 2n
>
>
> On Wed, May 18, 2011 at 4:44 PM, Kunal Patil <kp101...@gmail.com> wrote:
>
>> @Amit: Ohh..Your test case is correct but not my solution..[?]
>> It only works if it is guaranteed that one end will be at the extreme of
>> the array ! (UseLess ! [?])
>> Sorry folks...
>> So can anybody prove that O(n) solution does not exist for this problem?
>> [?]
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=100000655377926 *
>
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
<<35F.gif>>
<<33A.gif>>
<<330.gif>>
<<320.gif>>
