两层循环解决，找更小的就是了 时间复杂度n^2

function lengthOfLIS(nums: number[]): number {
    if(!nums.length) return 0;
    let dp:number[] = new Array(nums.length).fill(1);

    for(let i=1;i<nums.length;i++){
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j])
            dp[i] = Math.max(dp[i],dp[j]+1);
        }
    }
    return Math.max(...dp)
};

时间复杂度nlogn

function lengthOfLIS(nums: number[]): number {
    if (!nums.length) return 0;

    // tails[i]表示长度为i+1的递增子序列的最小结尾元素
    let tails: number[] = [];

    for (const num of nums) {
        // 二分查找num应该放在tails的位置
        let left = 0, right = tails.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        if (left === tails.length) {
            // 没找到大于等于num的元素，说明num比所有已有元素都大
            // 这意味着可以形成一个更长的递增子序列
            tails.push(num);
        } else {
            // 找到了大于等于num的元素，位置在left
            // 把该位置的值更新为num（更小或相等的值）
            tails[left] = num;
        }
    }

    return tails.length;
}