Longest increasing subsequence - Rosetta Code

Calculate and show here a longest increasing subsequence of the list:
{3,2,6,4,5,1}
And of the list:
{0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}
O(nlogn)
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;
}
}
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;

}

Read full article from Longest increasing subsequence - Rosetta Code