@Lucifer
I checked again and saw a few flaws in my code . Please ignore my prev post
.. :P
1) I am always comparing with q.front() and taking the diff but I should
also do the same with q.back() as it might contain values which have diff
>k . So yes , this is a bug
For this as you rightly pointed out we also need to compare with q.back()
So I modified my code accordingly
for(i=1;i<n;i++){
if(abs(a[i]-a[index.front()])>k || abs(a[index.back()]-a[i])>k ){
//binary_search(a,index,0,index.size()-1,i);
s=index.size();
cout<<a[i]<<" "<<s<<endl;
len=max(len,s);
while( (!index.empty()) && (abs(a[index.front()]-a[i])>k))
index.pop_front();
while( (!index.empty()) && (abs(a[index.back()]-a[i])>k))
index.pop_back();
}
For the second part that you said , yes potentially if we use queue.size()
we can miss out on continuous part ..
Thanks for pointing these out
Regards
Ankur
On Tue, Jan 3, 2012 at 4:06 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.
>>
>>
>
--
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.
