题解 | #最长递增子序列#

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here

        //tails[k]表示长度为k+1的最长递增子序列的末尾元素
        int[] tails = new int[arr.length];
        tails[0] = arr[0];
        int end = 0;
        //记录以当前元素为结尾的最长递增子序列的长度
        int[] maxLen = new int[arr.length];
        Arrays.fill(maxLen, 1);

        for (int i = 1; i < arr.length; i++) {
            int left = 0;
            int right = end + 1;

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (arr[i] > tails[mid]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = arr[i];
            if (left == end + 1) end++;
            if (left + 1 > maxLen[i]) maxLen[i] = left + 1;
        }

        int[] res = new int[end + 1];
        for (int i = arr.length - 1, j = res.length; j > 0; i--) {
            if (maxLen[i] == j) {
                res[--j] = arr[i];
            }
        }

        return res;
    }
}