最长递增子序列

动态规划

说明

tails[k] 记录长度 k+1 的递增子序列最小尾值；二分更新，时间 O(n log n)。

分析

tails[len−1] 保存某个长度的递增子序列可能达到的最小尾值。遇到新元素时，用二分找到第一个不小于它的位置并替换；这不会直接保存答案序列，但保留了未来延长的最好机会。

图解推演

对 [10,9,2,5,3,7]，tails 从 [10] 依次变成 [9]、[2]、[2,5]、[2,3]、[2,3,7]。将尾值 5 换成 3 不缩短已有长度，却使未来的 4 也能接上。严格递增使用第一个不小于 x 的位置，重复值不能增长长度。

查看图表代码

适用前提与边界

要重建序列，还需记录前驱下标。

示例输入与调用

fmt.Println(LIS([]int{10, 9, 2, 5, 3, 7}))

运行输出

3

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

func LIS(a []int) int {
	tails := []int{}
	for _, x := range a {
		i := sort.SearchInts(tails, x)
		if i == len(tails) {
			tails = append(tails, x)
		} else {
			tails[i] = x
		}
	}
	return len(tails)
}

func main() {
	fmt.Println(LIS([]int{10, 9, 2, 5, 3, 7}))
}