This problem asks:

Given: A positive integer n≤10000 followed by a permutation π of length n.

Return: A longest increasing subsequence of π, followed by a longest decreasing subsequence of π.

Required reading

  1. Subsequence
  2. Permutations
  3. Increasing subsequence
  4. Decreasing subsequence
  5. Longest increasing subsequence x2
  6. Patience sorting

Restate the problem

I’m going to get a number, n, followed by a list of n numbers in a random but specific order. I need to return the longest sequence of numbers from the order they were given where each number is greater than the previous number. Then, I need to do the same process in reverse, finding the longest decreasing sequence of numbers from the order they were given.

Solution steps

I read the pseudocode algorithm in the wikipedia article several times to try to understand how it worked.

Then, I found an algorithm on the wikipedia talk page that includes a python solution which I studied in depth.

I wrote the increasing subsequence and decreasing subsequence methods myself while referring to the Wikipedia article when stuck.

At the end, I needed to use long chains of string replacement commands to get rid of all the punctuation in the response before I wrote it to a file.