Longest Increasting Subsequence and Patience Sorting
What this dynamic programming problem and the Solitaire game have in common is the Patience Sorting algorithm. It's easy to see how the elements are arranged, but it's not obvious how to reconstruct the longest increasing subsequence.
Suppose you have this list of numbers (if you want to play with cards, take a look here):
3, 2, 4, 7, 1, 5, 9, 6, 8
Let's try building piles by using these values such that each number can be placed only in the first pile whose top is larger than our number (Solitare game like). If no such pile can be found, a new pile is created.
3, no pile found, it becomes the top of the new pile
2, it goes on first pile and becomes the new top
4, no pile found with larger top, create new pile
7, no pile found with larger top, create new pile
1, it goes on first pile and becomes the new top
5, it goes on the third pile and becomes the new top
9, no pile found with larger top, create new pile
6, it goes on the fourth pile and becomes the new top
8, no pile found with larger top, create new pile
Each time we add an element to a pile, we keep a reference to the top of the previous pile at that moment (if any), which represents, in fact, the previous element in the longest subsequence ending on the element we're adding.
Below how the piles look at the end (I added the references):
The number of piles represent the length of the longest increasing subsequence. We start with the top of the last pile and, by using references, we build the sequence.
Every time we add an element, we have to find the pile it belongs to. We are going to use a list that contains the top of each pile. This structure is ordered by the way of building it. Looking for the first element equal or greater than a value has the complexity of binary search, O(logN), therefore the time complexity of the algorithm is O(NlogN).
We will need additional structures for keeping the references and the piles, so the space complexity is O(N) (you can say P where P is the number of piles).
class HelperElement { public int Value { get; set; } public int? PreviousRef { get; set; } } public static IList<int> GetLongestIncreastingSubsequence(IList<int> list) { var result = new List<int>(); if (list.Count == 0) { return result; } var piles = new List<List<HelperElement>>(); var pileTops = new List<int>(); foreach (int element in list) { int pileIndex = 0; if (piles.Count == 0) { var pile = new List<HelperElement> { new HelperElement { Value = element } }; piles.Add(pile); } else { // find the pile to place the element pileIndex = Utils.FindFirstEqualOrHigher(pileTops, element, 0, pileTops.Count - 1); if (pileIndex == -1) { // no pile found, we'll create a new one pileIndex = piles.Count; piles.Add(new List()); } var pile = piles[pileIndex]; pile.Add(new HelperElement { Value = element }); // add pointer to the previous pile top element // will be used for tracking the sequence if (pileIndex > 0) { pile[pile.Count - 1].PreviousRef = piles[pileIndex - 1].Count - 1; } } if (pileTops.Count <= pileIndex) { pileTops.Add(element); } else { pileTops[pileIndex] = element; } } // build the longest increasing subsequence in descending order int? index = piles[piles.Count - 1].Count - 1; for (int i = piles.Count - 1; i >= 0; i--) { if (index.HasValue) { HelperElement element = piles[i][index.Value]; result.Add(element.Value); index = element.PreviousRef; } } // this can be avoided if the list is walked from right to end // searching for decreasing subsequences // however, it doesn't change complexity order result.Reverse(); return result; }
And if you want to take a look at the code that finds the first element equal or greater than a value:
public static int FindFirstEqualOrHigher(int[] array, int value, int left, int right) { if (left > right) { return -1; } if (left == right) { return array[left] >= value ? left : -1; } int half = left + (right - left) / 2; if (array[half] == value) { return half; } if (array[half] > value) { return FindFirstEqualOrHigher(array, value, left, half); } return FindFirstEqualOrHigher(array, value, half + 1, right); }