SOURCE

// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

let arr = [0, 3, 1, 6, 2, 2, 7]
// 解法一：动态规划
// 解题思路：

// 状态定义：
// dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。
// 转移方程： 设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：
// 1.当 nums[i] > nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j] + 1 ；
// 2.当 nums[i] <= nums[j] 时： nums[i] 无法接在nums[j] 之后，此情况上升子序列不成立，跳过。
// 上述所有 1. 情况 下计算出的 dp[j] + 1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)
// 转移方程： dp[i] = max(dp[i], dp[j] + 1) 。

// 初始状态：
// dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。

// 返回值：
// 返回 dp 列表最大值，即可得到全局最长上升子序列长度。

// 复杂度分析：
// 时间复杂度 O(N^2) ： 遍历计算 dp 列表需 O(N)，计算每个 dp[i] 需 O(N)。
// 空间复杂度 O(N) ： dp 列表占用线性大小额外空间。

function lengthOfLIS(nums = []) {
    if (nums.length < 2) return nums.length
    const dp = 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]) { //当nums[i] > nums[j]，则构成一个上升对
                dp[i] = Math.max(dp[i], dp[j] + 1) //更新dp[i]
            }
        }
    }
    console.log(dp)
    return Math.max(...dp)
}

console.log(lengthOfLIS(arr))


// 方法2.二分查找+贪心
// 思路：准备tail数组存放最长上升子序列，核心思想就是越小的数字越要往前放，
// 这样后面就会有更多的数字可以加入tails数组。将nums中的数不断加入tail，
// 当nums中的元素比tail中的最后一个大时 可以放心push进tail，
// 否则进行二分查找，让比较小的数二分查找到合适的位置，让后面有更多的数字与这个数形成上升子序列
// 复杂度：
// 时间复杂度O(nlogn)，n为nums的长度，每次二分查找需要logn，所以是总体的复杂度是O(nlogn)。
// 空间复杂度是O(n) ,tail数组的开销


function doubleLIS(nums = []) {
    const len = nums.length
    if (len < 2) return len
    let resArr = [arr[0]]
    for (let i = 1; i < len; i++) {
        if (nums[i] > resArr[resArr.length - 1]) {
            resArr.push(nums[i])
        } else {
            // 二分法
            let left = 0
            let right = resArr.length - 1
            while (left < right) {
                let mid = Math.floor((left + right) / 2)
                if (nums[i] > resArr[mid]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            resArr[left] = nums[i] //将nums[i]放置到合适的位置，此时前面的元素都比nums[i]小
        }
    }
    console.log(resArr)
    return resArr.length
}

console.log(doubleLIS(arr))

function lengthOfLIS1(nums) {
    let n = nums.length;
    if (n <= 1) {
        return n;
    }
    let tail = [nums[0]];//存放最长上升子序列数组
    for (let i = 0; i < n; i++) {
        if (nums[i] > tail[tail.length - 1]) {//当nums中的元素比tail中的最后一个大时 可以放心push进tail
            tail.push(nums[i]);
        } else {//否则进行二分查找
            let left = 0;
            let right = tail.length - 1;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tail[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tail[left] = nums[i];//将nums[i]放置到合适的位置，此时前面的元素都比nums[i]小
        }
    }
    console.log(tail)
    return tail.length;
}

lengthOfLIS1(arr)