Link : GONESORT

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, a

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, a

_{1},a_{2},a_{3}. . . a_{N}, and let the sorted sequence be b_{1},b_{2},b_{3}. . . b_{N}. Suppose the numbers b_{i},b_{i+1},b_{i+2}. . . b_{j}are such that in sequence {a}_{N}, they appear in same order (b_{i+k}occurs before b_{i+k+1}, but there can be other numbers apart from b_{i}to b_{j}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(N

^{2})

Code:

## No comments:

## Post a Comment