Long increase subsequences are study in the context of various disciplines associated to mathematics, including algorithmics, random matrix theory, representation theory, and physics. In computer science, the longest increase subsequence problem is to find a subsequence of a given sequence in which the subsequence's components are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

COMING SOON!

```
package DynamicProgramming;
import java.util.Scanner;
/**
* @author Afrizal Fikri (https://github.com/icalF)
*/
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ar[] = new int[n];
for (int i = 0; i < n; i++) {
ar[i] = sc.nextInt();
}
System.out.println(LIS(ar));
sc.close();
}
private static int upperBound(int[] ar, int l, int r, int key) {
while (l < r - 1) {
int m = (l + r) >>> 1;
if (ar[m] >= key)
r = m;
else
l = m;
}
return r;
}
private static int LIS(int[] array) {
int N = array.length;
if (N == 0)
return 0;
int[] tail = new int[N];
// always points empty slot in tail
int length = 1;
tail[0] = array[0];
for (int i = 1; i < N; i++) {
// new smallest value
if (array[i] < tail[0])
tail[0] = array[i];
// array[i] extends largest subsequence
else if (array[i] > tail[length - 1])
tail[length++] = array[i];
// array[i] will become end candidate of an existing subsequence or
// Throw away larger elements in all LIS, to make room for upcoming grater elements than array[i]
// (and also, array[i] would have already appeared in one of LIS, identify the location and replace it)
else
tail[upperBound(tail, -1, length - 1, array[i])] = array[i];
}
return length;
}
}
```