算法：最长增长序列300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

解答

这个算法其实就是。如果你把它想象成一堆卡片而不是尾巴，你可能会更容易理解它是如何工作的。桩数是最长子序列的长度。有关更多信息，请参阅。

下面的算法逻辑：

1. 初始化一个有序数组dp；
2. 遍历数组nums；
3. 如果下个数字比有序数组dp的最后一个数字还大，直接追加到末尾；
4. 否则找到刚好大于前一个数字，替换掉数字即可；为啥要这一步？想一想，已经有序的数字大小len是不变的，改变可以替换的数字，以防后面的要以小的开始排序用。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        dp[len++] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > dp[len -1]) {
                dp[len++] = nums[i];
            } else {
                // replace the value in the just right place
                dp[find(dp, 0, len - 1, nums[i])] = nums[i];
            }
        }
        
        return len;
    }
    
    private int find(int[] dp, int left, int right, int n) {
        while(left < right) {
            int mid = left + ((right - left) >> 2);
            if (dp[mid] >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

参考

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74880/JAVA-Easy-Version-To-Understand!!!