Wednesday, November 28, 2012



Category : Sequences, ad-hoc

Hint : What are the books that need not be moved. Try to find maximum set of such numbers.

Solution : Let the sequence be of N numbers, a1,a2,a3 . . . aN, and let the sorted sequence be b1,b2,b3 . . . bN. Suppose the numbers bi,bi+1,bi+2. . . bj are such that in sequence {a}N, they appear in same order  (bi+k occurs before bi+k+1, but there can be other numbers apart from bi to bj in between them). In this case, all numbers apart from this subsequence can be put to order in N-(j-i+1) steps.

Now the problem is to find maximum contiguous increasing sequence in given set (maximum length sequence such that it appears continuously in sequence {b}N and appears in increasing order in {a}N  It can be easily done in O(N2)


No comments:

Post a Comment