Given an array of random numbers. Find longest monotonically increasingsubsequence (LIS) in the array.
Patience. Deal cards c1, c2, …, cn into piles according to two rules:
・Can't place a higher-valued card onto a lowered-valued card.
・Can form a new pile and put a card onto it.
Goal. Form as few piles as possible.
Greedy algorithm. Place each card on leftmost pile that fits.
Weak duality.
In any legal game of patience, the number of piles ≥
length of any increasing subsequence.
Pf.
・Cards within a pile form a decreasing subsequence.
・Any increasing sequence can use at most one card from each pile.
Theorem. [Hammersley 1972] Min number of piles = max length of an IS;
moreover greedy algorithm finds both.
Pf. Each card maintains a pointer to top card in previous pile.
・Follow pointers to obtain IS whose length equals the number of piles.
・By weak duality, both are optimal.
Greedy algorithm: implementation
Theorem.
The greedy algorithm can be implemented in O(n log n) time.
・Use n stacks to represent n piles.
・Use binary search to find leftmost legal pile.
Patience sorting.
Deal all cards using greedy algorithm; repeatedly remove
smallest card.
Our observation is, assume that the end element of largest sequence is E. We can add (replace) current element A[i] to the existing sequence if there is an element A[j] (j > i) such that E < A[i] < A[j] or (E > A[i] < A[j] – for replace).
1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.
Ensure we have maintained the condition, “end element of smaller list is smaller than end elements of larger lists“.
Querying length of longest is fairly easy. Note that we are dealing with end elements only. We need not to maintain all the lists. We can store the end elements in an array. Discarding operation can be simulated with replacement, and extending a list is analogous to adding more elements to array.
We will use an auxiliary array to keep end elements. The maximum length of this array is that of input. In the worst case the array divided into N lists of size one (note that it does’t lead to worst case complexity). To discard an element, we will trace ceil value of A[i] in auxiliary array (again observe the end elements in your rough work), and replace ceil value with A[i]. We extend a list by adding element to auxiliary array. We also maintain a counter to keep track of auxiliary array length.
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
Let
S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.
Now iterate through every integer
X of the input set and do the following:- If
X> last element inS, then appendXto the end ofS. This essentialy means we have found a new largestLIS. - Otherwise find the smallest element in
S, which is>=thanX, and change it toX. BecauseSis sorted at any time, the element can be found using binary search inlog(N).
Total runtime -
N integers and a binary search for each of them - N * log(N) = O(N log N)
Now let's do a real example:
Set of integers:
2 6 3 4 1 2 9 5 8
Steps:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
So the length of the LIS is
5 (the size of S).
To reconstruct the actual
LIS we will again use a parent array. Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i.
To make things simpler, we can keep in the array
S, not the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep {4, 5, 3, 7, 8}.
That is input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5, input[8] = 8.
If we update properly the parent array, the actual LIS is:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Now to the important thing - how do we update the parent array? There are two options:
- If
X> last element inS, thenparent[indexX] = indexLastElement. This means the parent of the newest element is the last element. We just prependXto the end ofS. - Otherwise find the index of the smallest element in
S, which is>=thanX, and change it toX. Hereparent[indexX] = S[index - 1].
int LongestIncreasingSubsequenceLength(int A[], int size) { // Add boundary case, when array size is one int *tailTable = new int[size]; int len; // always points empty slot memset(tailTable, 0, sizeof(tailTable[0])*size); tailTable[0] = A[0]; len = 1; for( int i = 1; i < size; i++ ) { if( A[i] < tailTable[0] ) // new smallest value tailTable[0] = A[i]; else if( A[i] > tailTable[len-1] ) // A[i] wants to extend largest subsequence tailTable[len++] = A[i]; else // A[i] wants to be current end candidate of an existing subsequence // It will replace ceil value in tailTable tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]; } delete[] tailTable; return len;}int GetCeilIndex(int A[], int T[], int l, int r, int key) { int m; while( r - l > 1 ) { m = l + (r - l)/2; if( A[T[m]] >= key ) r = m; else l = m; } return r;}int LongestIncreasingSubsequence(int A[], int size) { // Add boundary case, when array size is zero // Depend on smart pointers int *tailIndices = new int[size]; int *prevIndices = new int[size]; int len; memset(tailIndices, 0, sizeof(tailIndices[0])*size); memset(prevIndices, 0xFF, sizeof(prevIndices[0])*size); tailIndices[0] = 0; prevIndices[0] = -1; len = 1; // it will always point to empty location for( int i = 1; i < size; i++ ) { if( A[i] < A[tailIndices[0]] ) { // new smallest value tailIndices[0] = i; } else if( A[i] > A[tailIndices[len-1]] ) { // A[i] wants to extend largest subsequence prevIndices[i] = tailIndices[len-1]; tailIndices[len++] = i; } else { // A[i] wants to be a potential condidate of future subsequence // It will replace ceil value in tailIndices int pos = GetCeilIndex(A, tailIndices, -1, len-1, A[i]); prevIndices[i] = tailIndices[pos-1]; tailIndices[pos] = i; } } cout << "LIS of given input" << endl; for( int i = tailIndices[len-1]; i >= 0; i = prevIndices[i] ) cout << A[i] << " "; cout << endl; delete[] tailIndices; delete[] prevIndices; return len;}int lis(int arr[], int N){ int i; set<int> s; set<int>::iterator k; for (i=0; i<N; i++) { // Check if the element was actually inserted // An element in set is not inserted if it is // already present. Please see if (s.insert(arr[i]).second) { // Find the position of inserted element in iterator k k = s.find(arr[i]); k++; // Find the next greater element in set // If the new element is not inserted at the end, then // remove the greater element next to it (This is tricky) if (k!=s.end()) s.erase(k); } } // Note that set s may not contain actual LIS, but its size gives // us the length of LIS return s.size();}
Longest increasing subsequence - Rosetta CodeO(nlogn)
Longest Monotonically Increasing Subsequence Size (N log N)
public static int[] lis(int[] a) {
int n = a.length;
int[] tail = new int[n];
int[] prev = new int[n];
int len = 0;
for (int i = 0; i < n; i++) {
int pos = lower_bound(a, tail, len, a[i]);
if (pos == len) {
++len;
}
prev[i] = pos > 0 ? tail[pos - 1] : -1;
tail[pos] = i;
}
int[] res = new int[len];
for (int i = tail[len - 1]; i >= 0; i = prev[i]) {
res[--len] = a[i];
}
return res;
}
static int lower_bound(int[] a, int[] tail, int len, int key) {
int lo = -1;
int hi = len;
while (hi - lo > 1) {
int mid = (lo + hi) >>> 1;
if (a[tail[mid]] < key) {
lo = mid;
} else {
hi = mid;
}
}
return hi;
}
http://robentan.blogspot.com/2011/11/more-efficient-algorithm-for-longest.html
Also refer to http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
http://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
Todo: http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
Read full article from Longest Monotonically Increasing Subsequence Size (N log N) | GeeksforGeeks
Longest Monotonically Increasing Subsequence Size (N log N)
public static <E extends Comparable<? super E>> List<E> lis(List<E> n) { List<Node<E>> pileTops = new ArrayList<Node<E>>(); // sort into piles for (E x : n) { Node<E> node = new Node<E>(); node.value = x; int i = Collections.binarySearch(pileTops, node); if (i < 0) i = ~i; if (i != 0) node.pointer = pileTops.get(i-1); if (i != pileTops.size()) pileTops.set(i, node); else pileTops.add(node); } // extract LIS from nodes List<E> result = new ArrayList<E>(); for (Node<E> node = pileTops.size() == 0 ? null : pileTops.get(pileTops.size()-1); node != null; node = node.pointer) result.add(node.value); Collections.reverse(result); return result; } private static class Node<E extends Comparable<? super E>> implements Comparable<Node<E>> { public E value; public Node<E> pointer; public int compareTo(Node<E> y) { return value.compareTo(y.value); } }http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
We have elements: 
.
.
And we have a longest increasing subsequences of them: 
, for any Ai,k(1 < = k < = j) you could not find a smaller alternative.
, for any Ai,k(1 < = k < = j) you could not find a smaller alternative.
Now we have a new element: ai + 1
What we can do about it:
1. insert it at the back if Ai,j < ai + 1, where we will have a longer one;
2. make it an alternative for Ai,k if 
Alternative means that we MIGHT get longer ones if using the new element.
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ void find_lis(vector<int> &a, vector<int> &b) { vector<int> p(a.size()); int u, v; if (a.empty()) return; b.push_back(0); for (size_t i = 1; i < a.size(); i++) { // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue if (a[b.back()] < a[i]) { p[i] = b.back(); b.push_back(i); continue; } // Binary search to find the smallest element referenced by b which is just bigger than a[i] // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity. for (u = 0, v = b.size()-1; u < v;) { int c = (u + v) / 2; if (a[b[c]] < a[i]) u=c+1; else v=c; } // Update b if new value is smaller then previously referenced value if (a[i] < a[b[u]]) { if (u > 0) p[i] = b[u-1]; b[u] = i; } } for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; }Java code at https://sites.google.com/site/indy256/algo/lis_nlogn
public static int[] lis(int[] a) {
int n = a.length;
int[] tail = new int[n];
int[] prev = new int[n];
int len = 0;
for (int i = 0; i < n; i++) {
int pos = lower_bound(a, tail, len, a[i]);
if (pos == len) {
++len;
}
prev[i] = pos > 0 ? tail[pos - 1] : -1;
tail[pos] = i;
}
int[] res = new int[len];
for (int i = tail[len - 1]; i >= 0; i = prev[i]) {
res[--len] = a[i];
}
return res;
}
static int lower_bound(int[] a, int[] tail, int len, int key) {
int lo = -1;
int hi = len;
while (hi - lo > 1) {
int mid = (lo + hi) >>> 1;
if (a[tail[mid]] < key) {
lo = mid;
} else {
hi = mid;
}
}
return hi;
}
http://robentan.blogspot.com/2011/11/more-efficient-algorithm-for-longest.html
Also refer to http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
http://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
Todo: http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
Read full article from Longest Monotonically Increasing Subsequence Size (N log N) | GeeksforGeeks
