写在前面，打算好好锻炼一下手撕的能力，之前 leetcode 也刷了挺多的，但是笔试基本都是 ACM 模式，有时候测试样例过了，但是通过率 0%很是头疼。于是希望通过ACM 模式，看是否能改善一点。
这里附上代码联系地址：牛客 ACM 刷题地址
牛客的 ACM 模式很多都没看到 python 的题解，所以自己打算边写边思索下。
Day 1：6 月 6 日
最长上升子序列
题目地址
第一版提交，没过：
n = int(input())
nums = list(map(int, input().split()))
max_ = 1
cur = 1
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
max_ = max(max_, dp[i])
print(max_)
(PS: 有一说一，提交一次挺久的，几十秒了)
中午或者下班再看看吧，不知道哪里错了😭
超时了估计
吃完晚饭，在跑代码的时候抽空想想……
不知道哪里有问题，交给 gpt 了，a 了……（这让人无语😅）
下面是 chtgpt4o 生成的，可以直接提交，看看人工智能的思路：
def length_of_lis(nums):
from bisect import bisect_left
if not nums:
return 0
dp = []
for num in nums:
pos = bisect_left(dp, num)
if pos < len(dp):
dp[pos] = num
else:
dp.append(num)
return len(dp)
# 读取输入
n = int(input().strip())
nums = list(map(int, input().strip().split()))
# 输出结果
print(length_of_lis(nums))
~~思路是这样的🤔
思路是来看就是遍历，维护一个严格递增的子序列；
按递增顺序添加末尾好理解，比较难 get 的是用二分查找去替换； 其实用小的把 dp 数组里面的大的去替换，可以理解为将 dp 数组做了一个 压紧操作（想象是一个弹簧）
比如序列是 1，2，7，5，6 那么一开始按顺序添加会得到【1、2、 7】
这个时候查找 5，对应做替换的是 7，因为 2 和 7 之间有太多空气，所以让 5 替换 7，做了压紧； 这样给了我们更多机会去把相对较大的数字给放进来（指的是 5
个人感觉那一步有点贪心的意思，动态规划没太感觉到。🤔
另外顺便学一下二分查找的懒人用法 bisect_left
这个是需要导入包的，bisect_left返回大于等于x的第一个下标
from bisect import bisect_left
index1 = bisect(List, x) #第1个参数是列表，第2个参数是要查找的数，返回值为索引
当然，我们真正手撕其实不太可能用这么偷懒的，毕竟一个二分操作的难度都可以手撕了，怎么可能放过你，下面附上那么精简的代码：
"""20240606 第二版"""
# 二分查找 Index
def Bisect(arr, n):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == n:
return mid
elif arr[mid] < n:
left = mid + 1
else:
right = mid - 1
return left
n = int(input())
nums = list(map(int, input().split()))
if len(nums) == 0:
print(0)
else:
dp = []
for i in range(n):
pos = Bisect(dp, nums[i])
if pos < len(dp):
dp[pos] = nums[i]
else:
dp.append(nums[i])
# print(dp)
print(len(dp))