-1
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

0
$\begingroup$

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]]
$\endgroup$
1
  • $\begingroup$ Thank you very much! This is an excellent way of doing it. $\endgroup$
    – Turtle
    Oct 31, 2018 at 11:04
1
$\begingroup$

Your problem is the well-known Longest Increasing Subsequence.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.