@Ankur..
A : 2 4 6 8 1, diff is 6.
Looks like the answer acc. to ur code would be 5, but actually it
should be 4..
I m correct, then it can be fixed by looking at the front and back of
the queue and see whether the A[i] is actually the curr min or curr
max..
And then calculate the diff based on the above cond i.e either
abs(A[i] - Q.front()) or abs(A[i] - Q.back())
Also,
Taking the size of queue for calculating the max is incorrect, as the
queue might contain elements with lower indices that actually
shouldn't be considered for subarray calculation...
Say, Queue : i j k l m
Now, it is possible that i < j and i > k...
Hence, if u remove i and then calculate the next subarray it will also
take k into consideration which is incorrect..
The max length should be : Q.back - (i + 1) for the next iteration...
basically 'i+1' should be the start index...
Also, say when the queue looks like: k l m , this state is incorrect..
While removing elements u should also look for indices, if the current
start index is grater than Q.front then u should remove Q.front...
i.t for k l m..
current start index would be 'j+1' and as k < j hence you should
remove it and loop over for further removals..
I all my observations are correct, then a couple of modifications will
rectify the code..
In case i m wrong.. then cheers :)
On Jan 3, 1:20 am, Lucifer <sourabhd2...@gmail.com> wrote:
> @ Optimization ... O(N).. single run O(n^2)
>
> Basically in a single run we can calculate the maximum value using
> praveen's logic..
>
> Say, A[N] is the array of integers..
>
> And X[N+1] stores the intermediate values for maximum size subarray...
>
> int max = 0;
> int strtind = -1;
> int endind = -1;
>
> for(int i =0; i<= N; ++i)
> X[i] = 0;
>
> for (int i = 0; i < N; ++i)
> for (j = N; j > 0; --j)
> {
> X[j] = ( abs(A[i] - A[j]) > K ) ? 0 : 1+ min( X[j],
> X[j-1] ) ;
> if ( A[j] > max)
> {
> max = A[j];
> strtind = i - max + 1;
> endind = j - 1;
> }
> }
>
> On Jan 3, 12:57 am, Lucifer <sourabhd2...@gmail.com> wrote:
>
>
>
>
>
>
>
> > @above..
> > I m sorry,
> > A would be 1 2 3 4 5 ..
>
> > On Jan 3, 12:03 am, atul anand <atul.87fri...@gmail.com> wrote:
>
> > > @praveen : i guess we can optimize the space to O(n);
>
> > > if diff b/w two number is <=K then A[i]=A[i-1]+1;
>
> > > if condition fails temp_maxLen=A[i-1];
> > > if(temp_maxlen > maxLen)
> > > {
> > > maxLen=temp_maxlen;
>
> > > }
--
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.
