Given a list of values, choose the greatest possible number of sorted values

Question

Given an array of numbers, I want to select some entries, preserving their order, so that I end up with the longest possible sorted sub-array. It does not matter which entries I discard in the process. In case it matters, each value may only appear once.

How might I attack this problem?

Examples:

[1, 3, 2] - > [1, 2]
[4, 1, 5, 2, 6, 3, 7] - > [4, 5, 6, 7]
[4, 5, 6, 1, 2, 3] - > [1, 2, 3] or [4, 5, 6]

Any help would be greatly appreciated.

Answer 1

My approach would be as follows.

I iterate through the input list, and at each step I consider the two possibilities:

• I either put the element in the result list if I can (that is, the current element is bigger then the last element)
• or I don't

While iterating, I maintain the set of partial solutions obtained so far.

As an optimization, I can remove from the set of partial solutions those that will not have the chance of becoming end solutions: at iteration $k$, if the longest partial solution has length $m$, I can remove all partial solutions whose length are smaller then $m-(n-k)$, where $n$ is the length of the initial list. This is because I can only grow the partial solution with $n-k$ elements in the best case.

Here is a sample run for [1,3,2]:

• iteration 1, partial solutions: [[1],[]]
• iteration 2, partial solutions: [[1,3],[3],[]]
• iteration 2, after filtering: [[1,3],[3]] (There is only one element left to visit, so I will not be able to extend [] to beat the [1,3] partial solution.)
• iteration 3, partial solutions: [[1,3],[3]]
• iteration 3, after filtering: [[1,3]]

Answer 2

Your problem is the well-known Longest Increasing Subsequence.

Wikipedia article contains details: https://en.wikipedia.org/wiki/Longest_increasing_subsequence