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 <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.