I think this can be solved in NlogN using binary search
Here is the idea
We take a deque which stores the index of the array in increasing order
i.e. the index with minimum value is always on the front of the deque
Now when a new element comes we check with the front of this deque .
If the diff of the front element of the deque and a[i] <=k that means it
can be part of the sequence . So we insert it into the correct position in
the deque using binary Search
If the diff is >k then we know that with this element the sequence cant be
formed .So we update the maxLength to max(maxLen,deque.size())
And then remove all the elements from front of the deque till which diff
between front and a[i]<=k
and keep on repeating the same process
We traverse the array once only and perform binary seach every time so
complexity nlogn
Ex array
2,1,8,12,10,15,13,25
I took deque as data structure so that I can insert and remove elements
from both ends and also access any in between element in O(1)
So Initially declare maxLen=INT_MIN
now 2 comes with index i=0
Since deque is empty we put its index -> Deque -> 0
Now next element is 1
We compare front of deque with 1 -> 2-1 =1 .Its less than 7 so we insert it
into correct position in deque using Binary Search
Deque ->1,0
Now 8 comes -Again 8-1 ==7 So we again put it in
Deque - > 1,0,2
Now comes 12
Now 12-1>7 So it cant be part of Sequence . So we need to remove the
elements . The deque will always contain elements which can be part of the
sequence
Before removing we update the maxLen= max(INT_MIN,deque.size()) so it
becomes 3 for Now
And now we remove elements from start of the deque until deque.front()-12
<=7
So deque becomes 2
Now insert 12 's index i.e 3 in correct position Deque -> 2,3
Now comes 10 ..It will be part of the sequence So insert it in
Deque -> 2,4,3
Now comes 15 .. Insert it as well
Dequeu-> 2,4,3,5
13 comes
Dequeue-> 2,4,3,6,5
Now comes 25
Update Max len=5 and start removing
Deque will only have 1 now
Now we are done with array
So we return 5
I wrote the code for this and it worked on few cases .I am sharing it below
, but I guess the idea is cleared as I stated above.
I dont think we can do better than NlogN here
Code ->
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);
binary_search(a,index,0,index.size()-1,i);
}
s=index.size();
len=max(len,s);
return len;
}
On Tue, Jan 3, 2012 at 1:50 AM, Lucifer <[email protected]> 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 <[email protected]> wrote:
> > @above..
> > I m sorry,
> > A would be 1 2 3 4 5 ..
> >
> > On Jan 3, 12:03 am, atul anand <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
