給定一個無序的整數(shù)數(shù)組屋谭，找到其中最長上升子序列的長度响蕴。

示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]窗看，它的長度是 4应役。
說明:

可能會有多種最長上升子序列的組合槽畔，你只需要輸出對應的長度即可。
你算法的時間復雜度應該為 O(n2) 鞍爱。
進階: 你能將算法的時間復雜度降低到 O(n log n) 嗎?

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作權(quán)歸領扣網(wǎng)絡所有鹃觉。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處睹逃。

解法一：動態(tài)規(guī)劃

class Solution {
    /**
     * 動態(tài)規(guī)劃
     * 1. 狀態(tài)定義：f(n)=從index=0到index=n中最長的上升子序列
     * 2. 轉(zhuǎn)移方程：f(n)=f(x)+num[n], {f(0), f(1), ..., f(n-1)}過濾最后一個元素小于nums[n],并從中找出最長的上升子序列的f(x)
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = 1;
        int[][] fn = new int[nums.length][];
        fn[0] = new int[]{nums[0]};
        for (int i = 1; i < nums.length; i++) {
            int[] beforeMaxLengthOfLIS = findBeforeMaxLengthOfLIS(fn, i, nums[i]);
            int newSize = beforeMaxLengthOfLIS != null ? beforeMaxLengthOfLIS.length + 1 : 1;
            int[] curLIS;
            if (beforeMaxLengthOfLIS == null) {
                curLIS = new int[1];
            } else {
                curLIS = Arrays.copyOf(beforeMaxLengthOfLIS, newSize);
            }
            curLIS[newSize - 1] = nums[i];
            fn[i] = curLIS;
            if (newSize > max) {
                max = newSize;
            }
        }
        return max;
    }

    /**
     * {f(0), f(1), ..., f(n-1)}過濾最后一個元素小于nums[n],并從中找出最長的上升子序列的f(x)
     *
     * @param fn
     * @param curNum
     * @return
     */
    private int[] findBeforeMaxLengthOfLIS(int[][] fn, int endIndex, int curNum) {
        int[] maxLength = null;
        int max = 0;
        for (int i = 0; i < fn.length; i++) {
            int[] list = fn[i];
            if (i >= endIndex || list[list.length - 1] >= curNum) {
                continue;
            }
            if (list.length > max) {
                max = list.length;
                maxLength = list;
            }
        }
        return maxLength;
    }
}

運行效率

解法二：定義一個最長上升子序列數(shù)組盗扇，只能添加或者更新，最終的長度就是最長的長度

class Solution {
    /**
     * 時間復雜度O(N*logN)
     * 
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        List<Integer> result = new ArrayList<>();
        result.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            // 當前元素大于數(shù)組中的所有元素沉填，添加在尾部
            if (result.get(result.size() - 1) < nums[i]) {
                result.add(nums[i]);
                continue;
            }
            // 二分查找疗隶，找到一個元素比當前元素大，前一個元素比當前元素小的元素翼闹，替換成當前元素
            int begin = 0, end = result.size() - 1, mid;
            do {
                mid = (begin + end) / 2;
                if (nums[i] > result.get(mid)) {
                    begin = mid + 1;
                } else {
                    end = mid;
                }
            } while (begin < end);
            result.set(begin, nums[i]);
        }
        return result.size();
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 4};
        int result = new Solution().lengthOfLIS(nums);
        System.out.println(result);
    }
}

運行效率