求数组的最长上升子序列的长度。

动态规划

dp[i]为考虑前i个元素，以第 i 个数字结尾的最长上升子序列的长度，nums[i] 必须被选取。

状态转移方程为
dp[i] = max(dp[j]) + 1，其中 0 <= j < i，且nums[j] < nums[i]

• 时间复杂度 O(n^2)，计算状态时dp[i]，需要O(n)遍历dp[0]-dp[i-1]
• 空间复杂度O(n)
• Runtime: 148 ms, faster than 69.52%
• Memory Usage: 39.3 MB, less than 82.00%

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let len = nums.length
    if(len === 0) return 0
    let dp = Array(len).fill(1)
    let max = 1
    for (let i = 1; i < len; i++) {
        for(let j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {
                if(dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1
                }
            }
        }
        if(max < dp[i]) max = dp[i]
    }
    return max
};

贪心 + 二分查找

若使上升子序列尽可能地长，需要让序列上升尽可能慢，因此希望每次在上升子序列最后加上的那个数尽可能小。

基于上述的贪心思路，维护一个数组dp[i]，表示长度为i的最长上升子序列的末尾元素的最小值，len记录目前最长上升子序列的长度，起始时 len 为 1，d[1] = nums[0]

dp[i] 基于i 是单调递增的。证明：前提 j < i，dp[j] >= dp[i]，考虑长度为 i 的最长上升子序列的末尾删除 i-j个元素，j的末尾元素小于d[i]且小于d[j]，找到长度为j的最长上升子序列，末尾元素小于 d[j]，得证。

依次遍历 nums 中的每个元素，更新数组 dp 和 len 的值，如果 nums[i] > nums[len]，则更新 len = len + 1，否则在 dp[1,...len] 中寻找 dp[i - 1] < nums[j] < dp[i]，可以根据数组的的单调性，使用二分查找寻找下标 i

• 时间复杂度O(nlogn)
• 空间复杂度O(n)
• Runtime: 80 ms, faster than 98.01% o
• Memory Usage: 39.1 MB, less than 93.13%

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let len = nums.length 
    if(len === 0) return 0
    let d = []
    d[1] = nums[0]
    let flag = 1
    
    for(let i = 1; i < len; i++) {
        if(d[flag] < nums[i]) {
            d.push(nums[i])
            flag++
        } else {
            let start = 1
            let end = flag
            let pos = 0
            while(start <= end) {
                let mid = (start + end) >> 1
                if(d[mid] < nums[i]) {
                    start = mid + 1
                    pos = mid
                } else {
                    end = mid -1
                }
            }
            d[pos + 1] = nums[i]
        }
    }
    return flag
};