@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.
#include <iostream>
#include <queue>
#include<cstdlib>
#include<climits>
using namespace std;
void binary_search(int a[],deque<int>&index,int low,int high,int i){
int mid;
deque<int>::iterator it;
it=index.begin();
while(low<=high){
mid=low+(high-low)/2;
if((mid==high || a[index[mid+1]]>=a[i]) && a[index[mid]]<= a[i]){
index.insert(it+mid+1,i);
return;
}
else if((mid==low || a[index[mid-1]]<=a[i]) && a[index[mid]]>= a[i] ){
if(mid==0){
index.insert(it,i);
return;
}else{
index.insert(it+mid-1,i);
return;
}
}
else if(a[index[mid]]<= a[i])
low=mid+1;
else if( a[index[mid]]>=a[i])
high=mid-1;
}
}
int FindMaxLength(int a[],int n,int k){
deque<int>index;
int len=INT_MIN;
int i,s;
index.push_back(0);
//length.push_back(0);
for(i=1;i<n;i++){
if(abs(a[i]-a[index.front()])>k){
//binary_search(a,index,0,index.size()-1,i);
s=index.size();
len=max(len,s);
while( (!index.empty()) && (abs(a[index.front()]-a[i])>k))
index.pop_front();
}
if(index.empty())
index.push_back(i);
else
binary_search(a,index,0,index.size()-1,i);
}
s=index.size();
len=max(len,s);
return len;
}
int main(){
int a[]={2 4 6 8 1};
int n=sizeof(a)/sizeof(a[0]);
int k;
cin>>k;
cout<<endl<<"ans is"<<FindMaxLength(a,n,k);
}
