LeetCode 第300题

第一种解法（基础方法）

function lengthOfLIS(nums: number[]): number {
  const arr = new Array(nums.length).fill(1)
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        arr[i] = Math.max(arr[i], arr[j] + 1)
      }
    }
  }
  return Math.max(...arr)
}

第二种解法

vue3源码通过思路解法，参考：packages/runtime-core/src/renderer.ts function getSequence(){}

function lengthOfLIS(nums: number[]): number {
    const indexArr = [0]
    const arr = nums.slice()
    const len = nums.length
    for(let i= 0; i < len; i++){
        if(nums[i] > nums[indexArr[indexArr.length-1]]){
            indexArr.push(i)
            arr[i] = indexArr[indexArr.length-2]
        }else{
            let left=0,right = indexArr.length-1
            while(left < right){
                const middleIndex = left+((right - left) >> 1)
                if(nums[indexArr[middleIndex]] < nums[i]){
                    left = middleIndex + 1
                }else{
                    right = middleIndex
                }
            }
            if(nums[indexArr[left]] > nums[i]){
                indexArr[left] = i
                if(left > 0){
                    arr[i] = left - 1
                }
            }
        }
    }
    return indexArr.length
};