@@ -0,0 +1,1382 @@
+import java.util.Arrays;%0A%0Apublic class LongestIncreasingSubsequence %7B%0A%0A%09public static void main(String%5B%5D args) %7B%0A%09%09int%5B%5D num = %7B0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15%7D;%0A%09%09int%5B%5D prev = new int%5Bnum.length%5D;%0A%09%09int%5B%5D next = new int%5Bnum.length + 1%5D;%0A%0A%09%09int length = 0;%0A%09%09for (int i = 0; i %3C num.length; i++) %7B%0A%09%09%09// binary search for the largest positive mid %3C= L such that%0A%09%09%09// num%5Bnext%5Bmid%5D%5D %3C num%5Bi%5D%0A%09%09%09int low = 1, high = length;%0A%09%09%09while (low %3C= high) %7B%0A%09%09%09%09int mid = (low + high) %3E%3E 1;%0A%09%09%09%09if (num%5Bnext%5Bmid%5D%5D %3C num%5Bi%5D)%0A%09%09%09%09%09low = mid + 1;%0A%09%09%09%09else%0A%09%09%09%09%09high = mid - 1;%0A%09%09%09%7D%0A%0A%09%09%09// After searching, low is 1 greater than the length of the longest%0A%09%09%09// prefix of num%5Bi%5D%0A%09%09%09// The predecessor of num%5Bi%5D is the last index of the subsequence of%0A%09%09%09// length low - 1%0A%09%09%09prev%5Bi%5D = next%5Blow - 1%5D;%0A%09%09%09next%5Blow%5D = i;%0A%0A%09%09%09// If we found a subsequence longer than any we've found yet, update%0A%09%09%09// length%0A%09%09%09length = Math.max(length, low);%0A%09%09%7D%0A%0A%09%09// Reconstruct the longest increasing subsequence%0A%09%09int%5B%5D ans = new int%5Blength%5D;%0A%09%09int index = next%5Blength%5D;%0A%09%09for (int i = length - 1; i %3E= 0; i--) %7B%0A%09%09%09ans%5Bi%5D = num%5Bindex%5D;%0A%09%09%09index = prev%5Bindex%5D;%0A%09%09%7D%0A%0A%09%09System.out.println(%22num: %22 + Arrays.toString(num));%0A%09%09System.out.println(%22prev: %22 + Arrays.toString(prev));%0A%09%09System.out.println(%22next: %22 + Arrays.toString(next));%0A%09%09System.out.println(%22ans: %22 + Arrays.toString(ans));%0A%09%7D%0A%0A%7D%0A

Create LongestIncreasingSubsequence.java