题解 | #最长上升子序列(三)#

package main


func LIS(arr []int) []int {
	n := len(arr)
	if n == 0 {
		return []int{}
	}
	// dp[i] 表示以arr[i]为结尾的序列的长度
	dp := make([]int, n)
	// p[i] 表示长度为i的序列的最后一个元素的最小值
	p := make([]int, n)
	end := 0
	dp[0] = 1
	p[0] = arr[0]
	for i := 1; i < n; i++ {
		if arr[i] > p[end] {
			end++
			p[end] = arr[i]
			dp[i] = end + 1
		} else {
			// 二分查找定位p中从左到右第一个大于等于arr[i]的数并替换掉它
            index := FindFirstLargeOrEqualIndex(p[:end+1],arr[i])
			p[index] = arr[i]
			dp[i] = index + 1
		}
	}
	res := make([]int, end+1)
	for i := n - 1; i >= 0; i-- {
		if dp[i] == end+1 {
			res[end] = arr[i]
			end--
		}
	}
	return res
}
func FindFirstLargeOrEqualIndex(arr []int, target int) int {
	left, right := 0, len(arr)
	for left < right {
		mid := (left + right) / 2
		if arr[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}