LongestIncreasingSubsequence.java

packagecom.jwetherell.algorithms.sequence;

/**
 * In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in 
 * which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. 
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest Increasing Subsequence Problem (Wikipedia)</a>
 * <br>
 * @author Bartlomiej Drozd <mail@bartlomiejdrozd.pl>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassLongestIncreasingSubsequence {

privateLongestIncreasingSubsequence() { }

/**
 * Longest increasing subsequence solved using dynamic programming. 
 */
publicstaticint[] getLongestIncreasingSubsequence(int[] X) {
finalint[] P = newint[X.length];
finalint[] M = newint[X.length+1];
intL = 0;
for (inti=0; i<X.length; i++) {
// Binary search for the largest positive j ≤ L such that X[M[j]] < X[i]
intlo = 1;
inthi = L;
while (lo <= hi) {
finalintmid = (int) Math.ceil((lo + hi) / 2);
if (X[M[mid]] < X[i])
lo = mid+1;
else
hi = mid-1;
 }

// After searching, lo is 1 greater than the length of the longest prefix of X[i]
finalintnewL = lo;

// The predecessor of X[i] is the last index of the subsequence of length newL-1
P[i] = M[newL-1];
M[newL] = i;

if (newL > L) {
// If we found a subsequence longer than any we've found yet, update L
L = newL;
 }
 }

// Reconstruct the longest increasing subsequence
finalint[] S = newint[L];
intk = M[L];
for (inti=L-1; i>=0; i--) {
S[i] = X[k];
k = P[k];
 }

returnS;
 }
}