in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #8

Algorithm 4.7: Given a set of n distinct numbers, find the length of the longest monotone increasing subsequence.

Example: [2 9 4 7 3 11 8] -> [2 4 7 11] with length 4

Quite an interesting problem. I thought and tried different approaches. Here’s the problem I had or which I neglected. I thought the problem required all subsets. The idea of the algorithm in the book is to find the largest sequence given an end and then compare the length appending the next element.

However, I thought that it wouldn’t work in a case like this:

I’m still wondering whether there’s a case in which we throw away a sequence which could work out as the longest one. Sadly, the author didn’t discuss the problem.

I see that there’s an inherent sub-structure. If we find the longest sequence in the last X numbers we can lengthen it by prepanding more stuff. Hm, thinking about it, that’s a good idea.

Let’s reverse the list:

[59 58 57 56 5 4 55 3 2]

Strangely, this does make more sense. Although, it’s probably equivalent. OK, new code.

We want a function which takes a list and returns a list with the largest subsets. More interesting however are the intermediate steps. We want it to give various things:

a) the current longest subsets
b) the next number

And it should return the longest subsets.

Let’s code. This took a while :D. So, we start with get-lengthy-subsets which returns a list of the largest subsets for each ‘level’.

Basically very straight forward. We start with a set with just one empty vector. Then check for each element in our set whether adding the next number is monotone bigger. We use the function get-increasing-coll for that. In case it is increasing, it returns the new vector with the number added. Otherwise it just returns the current variable.

This function uses increasing? which checks for the increment – which also works if we start with an empty vector.

The last function which helps us to get longest subset is easy:

We just sort by the length and select the last one. Done. Finally :D

Write a Comment


This site uses Akismet to reduce spam. Learn how your comment data is processed.