For input.. 6,7,1,5,4,10,8 K=8 Start - 0 , end - 6 It shud be start =0 , end = 4
On 3 Jan 2012 12:10, "Lucifer" <[email protected]> wrote: > > @atul.. > > Again :) an editing mistake... > Instead of A[j] it should be X[j]; > > i.e. > > * > if ( X[j] > max) > { > max = X[j]; > strtind = i - max + 1; > endind = j - 1; > } > * > > On Jan 3, 10:11 am, atul anand <[email protected]> wrote: > > @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 <[email protected]> wrote: > > > @Ankur.. > > > Missed ur post just by 2 mins.. > > > > > Great.. > > > ------------------------- > > > > > On Jan 3, 3:59 am, Lucifer <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> > > > 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 <[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. > > > > > > > > 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected] -- 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.
