Find the longest increasing subsequence in an array. If there are multiple, return one of them. Example, for [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], a longest increasing subsequence is [0, 2, 6, 9, 11, 15].
分析：
这题和找出长度不一样，找出长度，我们使用binary search找出当前值可以插入目前最长子序列的位置。但是一但插入以后，就不能还原。也就是说，当我们输出最长子序列的时候，排在数字x前面的数可能是在其后面。所以，我们需要用另一个数组来mantain当前值的predecessor值。
public class Solution { public int[] LIS(int[] arr) { int[] index = new int[arr.length]; int[] predecessor = new int[arr.length]; if (arr == null || arr.length == 0) { return arr; } predecessor[0] = -1; int maxLength = 1; for (int i = 1; i < arr.length; i++) { int idx = findInsertionPlace(arr, index, maxLength, arr[i]); if (idx == 0) { predecessor[i] = -1; } else { predecessor[i] = index[idx - 1]; } index[idx] = i; maxLength = Math.max(maxLength, idx + 1); } int lastNumberIndex = index[maxLength - 1]; int[] result = new int[maxLength]; for (int i = maxLength - 1; i >= 0; i--) { result[i] = arr[lastNumberIndex]; lastNumberIndex = predecessor[lastNumberIndex]; } return result; } private int findInsertionPlace(int[] arr, int[] index, int maxLength, int num) { int low = 0, high = maxLength - 1; while (low <= high) { int mid = (high - low) / 2 + low; if (arr[index[mid]] < num) { low = mid + 1; } else if (arr[index[mid]] == num) { return mid; } else { high = mid - 1; } } return low; } }
Longest Increasing Subsequence
原文：https://www.cnblogs.com/beiyeqingteng/p/11297088.html