今日刷题量：4
当前刷题总量：163
Easy: 62
Mid: 92
Hard: 9
Day44
解题思想
1143 最长公共子序列 LCS
- 本质：两个字符串的“最长公共子序列”（不要求连续，可跳过字符）。
- DP 核心思想：看末尾字符相不相等。
- dp[i][j]：text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度
- 转移：
- 若 a[i-1]==b[j-1]：dp[i][j]=dp[i-1][j-1]+1
- 否则：dp[i][j]=max(dp[i-1][j], dp[i][j-1])
- 初始化：dp[0][*]=dp[*][0]=0
- 可一维优化：用 dp[j] + prev 保存左上角
1035 不相交的线（Uncrossed Lines）
- 本质：其实就是 数组版 LCS（两个数组的最长公共子序列）。
- 线不相交 ⇔ 匹配的下标必须保持相对顺序 ⇔ 子序列。
- 直接套 1143 的 DP：
- dp[i][j]：A[0..i-1] 和 B[0..j-1] 最多能连几条不相交线
- 相等：dp[i-1][j-1]+1
- 不等：max(dp[i-1][j], dp[i][j-1])
53 最大子数组和
- 本质：一段连续子数组的最大和（必须连续）。
- Kadane / DP 核心思想：以 i 结尾的最优子数组，要么接上前面，要么从自己重开。
- cur：以当前位置结尾的最大子数组和
- 转移：cur = max(nums[i], cur + nums[i])
- ans = max(ans, cur)
- O(n) 时间、O(1) 空间
392 判断子序列
- 本质：s 是否能按顺序在 t 中“依次匹配出来”（不要求连续）。
- 核心思想：双指针线性扫描。
- 指针 i 扫 s、j 扫 t：
- 若 s[i]==t[j]：i++
- j++ 一直走
- 最后 i==|s| 则 true
- 进阶（大量查询同一 t）：
- 预处理 next[pos][ch] 跳表 → 每次 O(|s|)
- 或字符位置列表 + 二分 → 每次 O(|s| log|t|)
练习题目
1143.最长公共子序列(mid):https://leetcode.cn/problems/longest-common-subsequence/
1035.不相交的线(mid):https://leetcode.cn/problems/uncrossed-lines/description/
53. 最大子序和(mid):https://leetcode.cn/problems/maximum-subarray/
392.判断子序列(easy):https://leetcode.cn/problems/is-subsequence/description/