@Lucifier :
*if ( A[j] > max)
{
max = A[j];
strtind = i - max + 1;*
i am not getting this in your code :-
say if input is :- 1,2,3,4,5,6,100
K=8;
A[j]=100;
then
(100 > max)
{
max=100;
* strtind= i - 100 +1;
}
*
On Tue, Jan 3, 2012 at 4:33 AM, Lucifer <sourabhd2...@gmail.com> wrote:
> @Ankur..
> Missed ur post just by 2 mins..
>
> Great..
> -------------------------
>
> On Jan 3, 3:59 am, Lucifer <sourabhd2...@gmail.com> wrote:
> > @ Ankur,,
> >
> > Also, in the statement..
> > *
> > Then yes it is possible that i < j and i > k... but a[i] is
> > always
> > less
> > than a[j] and a[k]...
> > *
> > * but a[i] always less* - by a[i] i meant the latest element accessed
> > and not the element positioned at Q.front which is nothing but element
> > at index 'i'
> >
> > Hence, the actual statement should be,
> > *
> > Then yes it is possible that i < j and i > k... but a[R] is
> > always less than a[j] and a[k]...
> > *
> > R is basically the latest element accessed..
> >
> > On Jan 3, 3:56 am, Lucifer <sourabhd2...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @Ankur..
> > > I just executed ur code and i m getting 5, instead of 4..
> >
> > > Also,
> > > *
> > > Then yes it is possible that i < j and i > k... but a[i] is always
> > > less
> > > than a[j] and a[k]...
> > > *
> >
> > > Yes u r right.. but, then when u are calculating the size u are also
> > > by default including the element at index K which might not be the
> > > part of subarray..
> >
> > > Proof by contradiction:
> > > -----------------------------
> > > Say u remove index 'i', that means u subarray now starts from an
> index> i..
> >
> > > Now, your queue is : j k l m
> > > Say it grows till a point: X i.e j k l m ..X
> > > Now, you are calculating the size as the size of queue,
> > > that means u r also including element indexed at position 'k' from the
> > > original array..
> > > But we already know that the start of the subarray index is > 'i' as
> > > we just popped 'i' out in the previous iteration.
> >
> > > Hence, k cannot be considered while calculating the size of max
> > > array..
> >
> > > -------------------------------------------------
> >
> > > What do u think?
> > > ----------------------------------------------------
> >
> > > On Jan 3, 3:36 am, Ankur Garg <ankurga...@gmail.com> wrote:
> >
> > > > @Lucifer
> >
> > > > I checked with my code
> >
> > > > The answer is coming out to be 4 ..So in this case its passing
> >
> > > > Also the queue is containing the indexes in order of increasing
> values ..so
> > > > for curr min we need to only check the front of the queue.
> >
> > > > Also I remove the elements of the queue till all the diff of
> elements in
> > > > the queue with the current element is <=k
> >
> > > > If queue is containing elements
> > > > say
> > > > i j k l m
> >
> > > > Then yes it is possible that i < j and i > k... but a[i] is
> always less
> > > > than a[j] and a[k]...
> >
> > > > So queue will always contain the correct elements I guess..
> >
> > > > Like I said I have not done its testing with many cases .. But for
> this
> > > > case the answer is coming out correct
> >
> > > > One correction to the code though
> > > > it should be
> > > > if(index.empty())
> > > > index.push_back(i);
> > > > else
> > > > binary_search(a,index,0,index.size()-1,i);
> >
> > > > I missed the else part here..
> >
> > > > In case you find anyother case it would be great .. I am sharing the
> source
> > > > codes .cpp file
> >
> > > > If u find any case thats missing ..please tell me and I will also
> update in
> > > > case some case misses out
> >
> > > > Thanks very much for looking into it :)
> >
> > > > Thanks and Regards
> > > > Ankur
> >
> > > > On Tue, Jan 3, 2012 at 3:26 AM, Lucifer <sourabhd2...@gmail.com>
> wrote:
> > > > > @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.
> >
> > > > MaxdiffK.cpp
> > > > 1KViewDownload
>
> --
> 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.
>
>
--
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.
