LongestIncreasingSubsequence.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * @author Afrizal Fikri (https://github.com/icalF)
 */
publicfinalclassLongestIncreasingSubsequence {
privateLongestIncreasingSubsequence() {
 }

privatestaticintupperBound(int[] ar, intl, intr, intkey) {
while (l < r - 1) {
intm = (l + r) >>> 1;
if (ar[m] >= key) {
r = m;
 } else {
l = m;
 }
 }

returnr;
 }

publicstaticintlis(int[] array) {
intlen = array.length;
if (len == 0) {
return0;
 }

int[] tail = newint[len];

// always points empty slot in tail
intlength = 1;

tail[0] = array[0];
for (inti = 1; i < len; i++) {
// new smallest value
if (array[i] < tail[0]) {
tail[0] = array[i];
 } // array[i] extends largest subsequence
elseif (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];
 }
 }

returnlength;
 }

/**
 * @author Alon Firestein (https://github.com/alonfirestein)
 */
// A function for finding the length of the LIS algorithm in O(nlogn) complexity.
publicstaticintfindLISLen(int[] a) {
finalintsize = a.length;
if (size == 0) {
return0;
 }
int[] arr = newint[size];
arr[0] = a[0];
intlis = 1;
for (inti = 1; i < size; i++) {
intindex = binarySearchBetween(arr, lis - 1, a[i]);
arr[index] = a[i];
if (index == lis) {
lis++;
 }
 }
returnlis;
 }

// O(logn)

privatestaticintbinarySearchBetween(int[] t, intend, intkey) {
intleft = 0;
intright = end;
if (key < t[0]) {
return0;
 }
if (key > t[end]) {
returnend + 1;
 }
while (left < right - 1) {
finalintmiddle = (left + right) >>> 1;
if (t[middle] < key) {
left = middle;
 } else {
right = middle;
 }
 }
returnright;
 }
}