Leetcode解题报告——300. Longest Increasing Subsequence

题目要求：
Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

题目大意：
找出给定数组中的最长增长序列

解题思路：
首先想到用动态规划解决该问题，维护数组 dp , dp[i] 表示以第i个元素为结尾的增长序列的长度，则递归式为：
dp[i]= Math.max( dp[j] + 1 ,1) 其中 j < i && nums[j] < nums[i]

代码如下：

public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length ==0) return 0;
        
       int [] dp = new int[nums.length];
        dp[0] = 1;
        int lenght = 1;
        for (int i = 1; i <nums.length ; i++) {
            for (int j = i-1; j >= 0 ; j--) {
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            dp[i] = Math.max(dp[i],1);
            lenght = Math.max(lenght,dp[i]);
        }

        return lenght;
    }

后来发现有更巧妙的解题方法，时间复杂度减少到 nlog(n),在此做下笔记：
维护一个整数 len 代表当前最长增长序列的长度，一个数组 dp , 数组内维护着当前最长增长序列的最小序列，尽管从原序列顺序看来，它完全不符合，但这丝毫不影响结果。比如：
nums [ 1，4，3，8，2，10]
正常的增长序列为： [1，4，8，10] 或 [1，3，8，10]
而dp 中的序列为：[1，2，8，10]

参考代码如下：

public int lengthOfLIS(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int len = 0;
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > dp[len]) {
            dp[++len] = nums[i];
        }
        else {
            int index = search(dp, len, nums[i]);
            dp[index] = nums[i];
        }
    }
    return len + 1;
}

private int search(int[] dp, int len, int val) {
    int start = 0;
    while(start <= len) {
        int mid = start + (len - start) / 2;
        if(dp[mid] == val) {
            return mid;
        }
        else if(dp[mid] < val) {
            start = mid + 1;
        }
        else {
            len = mid - 1;
        }
    }
    return start;
}

参考文章：
O(nlogn) Clean and easy Java DP + Binary Search solution with detailed explanation