This mainly focuses on dynamic programming O(N^2) solution.
Longest increasing subsequence - Rosetta Code
Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks
Calculate and show here a longest increasing subsequence of the list
O(nlogn)
Longest Monotonically Increasing Subsequence Size (N log N)
A solution based on patience sorting, except that it is not necessary to keep the whole pile, only the top (in solitaire, bottom) of the pile, along with pointers from each "card" to the top of its "previous" pile.
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);
}
@Override
public String toString() {
return "v:" + value.toString() + ", p:" +pointer;
}
}
https://codepair.hackerrank.com/paper/3LJ7lrgM?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
static 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
for(int i=0;i<size;++i)
tailTable[i] = 0;
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];
}
return len;
}
http://www.cnblogs.com/lishiblog/p/4190936.html
http://blog.xiaohuahua.org/2015/01/26/lintcode-longest-increasing-subsequence/
Scala Version:
https://codepair.hackerrank.com/paper/m6hqnx4f?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
Using Dynamic Programming: O(n*n)
Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks
Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n
So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.
Following is a tabluated implementation for the LIS problem.
max_ref is global solution, return value is the local solution.
Print solution:
https://sites.google.com/site/indy256/algo/lis
public static int[] getLIS(int[] x) {
int n = x.length;
int[] len = new int[n];
Arrays.fill(len, 1);
int[] pred = new int[n];
Arrays.fill(pred, -1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (x[j] < x[i] && len[i] < len[j] + 1) {
len[i] = len[j] + 1;
pred[i] = j;
}
}
}
int bi = 0; // find max, we can calculate max during last step.
for (int i = 1; i < n; i++) {
if (len[bi] < len[i]) {
bi = i;
}
}
int cnt = len[bi];
int[] res = new int[cnt];
for (int i = bi; i != -1; i = pred[i]) {
res[--cnt] = x[i];
}
return res;
}
O(NlogN) solution: http://massivealgorithms.blogspot.com/2014/08/longest-monotonically-increasing.html
Todo: http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
Longest increasing subsequence - Rosetta Code
Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks
Calculate and show here a longest increasing subsequence of the list
O(nlogn)
Longest Monotonically Increasing Subsequence Size (N log N)
A solution based on patience sorting, except that it is not necessary to keep the whole pile, only the top (in solitaire, bottom) of the pile, along with pointers from each "card" to the top of its "previous" pile.
The loop runs for N elements. In the worst case (what is worst case input?), we may end up querying ceil value using binary search (log i) for many A[i].
Therefore, T(n) < O( log N! ) = O(N log N). Analyse to ensure that the upper and lower bounds are also O( N log N ). The complexity is THETA (N log N).
// Binary search (note boundaries in the caller) // A[] is ceilIndex in the caller static int CeilIndex(int A[], int l, int r, int key) { while (r - l > 1) { int m = l + (r - l)/2; if (A[m]>=key) r = m; else l = m; } return r; } static 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 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]; } return len; }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);
}
@Override
public String toString() {
return "v:" + value.toString() + ", p:" +pointer;
}
}
https://codepair.hackerrank.com/paper/3LJ7lrgM?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
static 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
for(int i=0;i<size;++i)
tailTable[i] = 0;
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];
}
return len;
}
http://www.cnblogs.com/lishiblog/p/4190936.html
http://blog.xiaohuahua.org/2015/01/26/lintcode-longest-increasing-subsequence/
Scala Version:
https://codepair.hackerrank.com/paper/m6hqnx4f?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
Using Dynamic Programming: O(n*n)
Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks
Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n
So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.
Following is a tabluated implementation for the LIS problem.
int lis( int arr[], int n ){ int *lis, i, j, max = 0; lis = (int*) malloc ( sizeof( int ) * n ); /* Initialize LIS values for all indexes */ for ( i = 0; i < n; i++ ) lis[i] = 1; /* Compute optimized LIS values in bottom up manner */ for ( i = 1; i < n; i++ ) for ( j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Pick maximum of all LIS values */ for ( i = 0; i < n; i++ ) if ( max < lis[i] ) max = lis[i]; /* Free memory to avoid memory leak */ free( lis ); return max;}max_ref is global solution, return value is the local solution.
int _lis( int arr[], int n, int *max_ref){ /* Base case */ if(n == 1) return 1; int res, max_ending_here = 1; // length of LIS ending with arr[n-1] /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs to be updated, then update it */ for(int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall max. And update the // overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here;}// The wrapper function for _lis()int lis(int arr[], int n){ // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis( arr, n, &max ); // returns max return max;}Print solution:
https://sites.google.com/site/indy256/algo/lis
public static int[] getLIS(int[] x) {
int n = x.length;
int[] len = new int[n];
Arrays.fill(len, 1);
int[] pred = new int[n];
Arrays.fill(pred, -1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (x[j] < x[i] && len[i] < len[j] + 1) {
len[i] = len[j] + 1;
pred[i] = j;
}
}
}
int bi = 0; // find max, we can calculate max during last step.
for (int i = 1; i < n; i++) {
if (len[bi] < len[i]) {
bi = i;
}
}
int cnt = len[bi];
int[] res = new int[cnt];
for (int i = bi; i != -1; i = pred[i]) {
res[--cnt] = x[i];
}
return res;
}
O(NlogN) solution: http://massivealgorithms.blogspot.com/2014/08/longest-monotonically-increasing.html
Todo: http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
1. Design an algorithm to construct the longest increasing list. Also, model your solution using DAGs.
2. Design an algorithm to construct all increasing lists of equal longest size.
3. Is the above algorithm an online algorithm?
4. Design an algorithm to construct the longest decreasing list..
http://www.jiuzhang.com/qa/232/
(1)如果要返回所有最长的具体的子序列而不是只返回长度，应该怎么做
(2)如果数组里面有duplicate，有什么影响
(3)如果输入是streaming的数组，设计一个每新来一个数字就即时计算从开始到现在的最长递增子序列问题的系统，如何设计
(4)接第(3)问，如果允许计算近似值，结果不一定是准确的值，可以怎么设计，如果streaming的数据有一定的规律，例如知道均值和方差，如何设计这个系统
Read full article from Longest increasing subsequence - Rosetta Code