最长递增子序列：回头看所有更小的
子序列可以跳着选。走到每个位置只问：前面哪个更小的结尾，接上自己能变得更长。tails 另外记「同样长度里结尾最小的那个」。
dp[i] = 1 + 前面所有 nums[j] < nums[i] 的 dp[j] 最大值；答案是 max(dp)。tails[k] 存长度为 k+1 的递增子序列的最小结尾，新数用二分找替换位置，时间从 O(n²) 降到 O(n log n)。空间都是 O(n)。
给你一个整数数组，找出一个严格递增的子序列，使它最长，返回这个长度。子序列可以跳着选，不必挨在一起；但相对顺序不能改，也不能拿相等的数来充数。
主例 nums = [10, 9, 2, 5, 3, 7, 101, 18]。一条长度为 4 的递增子序列是 2、3、7、101，也可以是 2、5、7、18。答案是 4，不要求你把序列本身交回去。
枚举每个数选或不选是 2ⁿ 条路径。本文要回答：为什么只要问「以当前数结尾的最长递增长度」，tails 数组里每个位置到底记的是什么，以及主例里 4 是怎样一步步长出来的。
以谁结尾，决定能接在谁后面
第一直觉是枚举所有子序列，留下严格递增里最长的。主例 8 个数，子集有 256 个，还能做；再长就要爆。另一种错觉是当成子数组，只看连续一段：主例连续递增最长是 2、5 或 3、7 或 7、101，长度 2，小于 4。子序列允许中间挖空，2 后面可以跳过 5 去接 3。
缺的不是「哪一条最长」这张名单，而是一个可以递推的小问题：以 nums[i] 结尾的递增子序列，最长能有多长。当前这个数必须当尾巴，所以它前面只能接一个值更小的位置 j。所有合法 j 里，谁的 dp[j] 最大，就在谁后面加 1。没有任何更小的前驱时，它只能自己单干，长度是 1。
开一个和数组一样长的 dp，每个位置先写成 1。i 从左往右走，对每个 i 再扫一遍 j=0..i-1：只有 nums[j] < nums[i] 时才尝试 dp[i] = max(dp[i], dp[j]+1)。全部填完，答案是 dp 里的最大值，不是最后一个格子——最长那条不一定以数组末尾结尾。
用手走主例。10、9、2 前面都没有更小的，dp 前三格都是 1。下标 3 的 5 只有 2 比它小，dp[3]=2，对应 2→5，演示停在这一格。下标 4 的 3 同样只能接 2，dp[4]=2。下标 5 的 7 能接 2、5、3，最长前驱是 2，再加 1 得 3，对应 2→3→7。
下标 6 的 101 前面个个更小，最长前驱是 7 的 3，再加 1 得 4，对应 2→3→7→101。下标 7 的 18 接得上 2、5、3、7，接不上 10、9、101，最长仍是 3+1=4。整表 [1,1,1,2,2,3,4,4]，答案 4。
还想再快，要换一本账。dp 问的是「以 i 结尾」，所以必须回头看所有 j。如果只关心长度，可以维护 tails：tails[k] 表示「目前所有长度为 k+1 的递增子序列里，结尾最小的那个数」。结尾更小，将来更好接。新来一个 x，若 x 比 tails 里所有结尾都大，就在末尾开一截，长度加一；否则在 tails 里二分，找到第一个 ≥ x 的位置，用 x 换掉它——同样长度，尾巴改瘦。
主例用 tails 再走一遍。10 进袋得 [10]；9 换掉 10 得 [9]；2 换掉 9 得 [2]。5 比 2 大，接上成 [2,5]；3 换掉 5 成 [2,3]；7 接上成 [2,3,7]。101 接上成 [2,3,7,101]；18 换掉 101 成 [2,3,7,18]。tails 长度始终是 4，和 dp 的答案一致。
注意 tails 本身不一定是某条真实子序列，它只是「每个长度的最瘦尾巴」。patience 这个名字来自纸牌：每堆只收更小的牌，新牌找不到堆就新开一堆，堆数就是最长递增长度。
相等不能接。题目要严格递增，nums[j] == nums[i] 时 dp 不能加一，tails 里也是用 x 去替换第一个 ≥ x 的位置，而不是追加。只要长度、不要序列时，看 max(dp) 或 len(tails) 即可；若要还原序列，dp 还得另记前驱下标。
非连续子序列可以跳着选，子数组必须连续。主例若禁止跳跃，最长递增只有 2。tails 能加速，是因为我们放弃了「以谁结尾」这份位置信息，只保留「每个长度的最瘦尾巴」。
Go：O(n²) DP
func lengthOfLIS(nums []int) int {dp := make([]int, len(nums))best := 0for i := range nums {dp[i] = 1for j := 0; j < i; j++ {if nums[j] < nums[i] && dp[j]+1 > dp[i] {dp[i] = dp[j] + 1}}if dp[i] > best { best = dp[i] }}return best}
1每个位置先写成 1：最差也能自己单干。best 边填边更新，避免最后再扫一遍。
2j 必须在 i 左边，且值严格更小，才能作为前驱。相等不加一。
3主例走到 5、7、101 时，dp 分别变成 2、3、4，和演示三帧标出的链条一致。答案取全程最大，不是 dp 末格。
总结
以 i 结尾：接在前面更小的最长者后面；tails 只记每个长度的最瘦尾巴。主例答案 4。
- 子序列可跳不可乱序。当成连续子数组，主例只能得到 2。
- dp[i] 回头看所有更小的 j。主例表是 [1,1,1,2,2,3,4,4]。
- tails[k] 是长度 k+1 的最小结尾，二分替换后长度仍是 LIS；它本身不必是一条真实序列。