摘要
Title: 895. 最长上升子序列
Tag: dp、LIS模型、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

895. 最长上升子序列

• 题意

  给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

• 思路

  dp

  • 

  二分

  • 思想就是，维护一个递增的答案数组，每次来了新数就二分答案数组，找第一个大于等于它的数
    • 如果找到了，说明这个数一定比找到的数更小，更优，取代即可
    • 没找到，说明比所有的都大，加至末尾即可

• 代码

  dp

  N = 1100
  
  dp, a = [0] * N, [0] * N
  n = int(input())
  
  a[1:] = map(int, input().split())
  
  
  for i in range(1, n + 1):
      dp[i] = 1
      for j in range(1, i + 1):
          if a[i] > a[j]:
              dp[i] = max(dp[i], dp[j] + 1)
  
  res = 0
  for i in range(1, n + 1):
      res = max(res, dp[i])
  print(res)

  ---

  二分

  '''
  Author: NEFU AB-IN
  Date: 2022-03-23 19:20:33
  FilePath: \ACM\Acwing\895.1.py
  LastEditTime: 2022-03-23 19:21:43
  '''
  from bisect import bisect_left
  
  n = int(input())
  
  a = list(map(int, input().split()))
  stk = []
  
  for i in range(n):
      idx = bisect_left(stk, a[i])
      if idx == len(stk):
          stk.append(a[i])
      else:
          stk[idx] = a[i]
  
  print(len(stk))