用动态规划解决爬楼梯、最大子数组和与最长递增子序列。

function climbStairs(n) {
  if (!Number.isInteger(n) || n < 0) throw new RangeError('n 必须是非负整数')
  let a = 1
  let b = 1
  for (let i = 2; i <= n; i++) {
    const next = a + b
    a = b
    b = next
  }
  return b
}

function maxSubArray(nums) {
  if (nums.length === 0) throw new RangeError('数组不能为空')
  let current = nums[0]
  let best = nums[0]
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i])
    best = Math.max(best, current)
  }
  return best
}

function lengthOfLIS(nums) {
  const tails = []
  for (const value of nums) {
    let lo = 0
    let hi = tails.length
    while (lo < hi) {
      const mid = (lo + hi) >> 1
      if (tails[mid] < value) lo = mid + 1
      else hi = mid
    }
    tails[lo] = value
  }
  return tails.length
}