最长递增子序列

问题

https://leetcode.cn/problems/longest-increasing-subsequence/

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

解法

动态规划

如果记录下数组每个位置的含自身的前面最长递增子序列，会发现一点规律：

位置偏后的最长递增子序列存在这样的关系，假设最长递增子序列长度用数组 dp表示，位置 j<i，则有 dp[i]=max(dp[i],dp[j]+1)。

那么这正是动态规划的场景。

func max(data ...int) int {
	m := math.MinInt
	for _, d := range data {
		if d > m {
			m = d
		}
	}
	return m
}

func lenOfLIS1(data []int) int {
	len := len(data)
	if len < 1 {
		return 0
	}
	// 最终的最长递增子序列长度
	result := 1
	// dp[i] 记录0~i包含 data[i] 的最长递增子序列的长度
	dp := make([]int, len)
	for i := 0; i < len; i++ {
        // i 位置，至少有一个只包含 data[i] 的自增子序列
		dp[i] = 1
		for j := 0; j < i; j++ {
			if data[i] > data[j] {
				// data[i] > data[j] 的情况下，要么 dp[i] 维持不变，要么比dp[j]大1
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		if dp[i] > result {
			result = dp[i]
		}
	}
	fmt.Println(dp)
	return result
}

func main() {
	var d1 = []int{}
	// d1,len of lis: 0
	fmt.Println("d1,len of lis:", lenOfLIS1(d1))

	var d2 []int
	// d2,len of lis: 0
	fmt.Println("d2,len of lis:", lenOfLIS1(d2))

	var d3 = []int{2, 1, 5, 3, 6, 4, 8, 9, 7}
	// d3,len of lis: 5
	fmt.Println("d3,len of lis:", lenOfLIS1(d3))

	var d4 = []int{2, 5, 1, 0}
	// d4,len of lis: 2
	fmt.Println("d4,len of lis:", lenOfLIS1(d4))
}

时间复杂度 \(O(n^2)\)，空间复杂度\(O(n)\)。

贪心

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能小。 维护一个数组 d，表示最长上升子序列的末尾元素的最小值。

d[i]是关于 i 单调递增的。

遍历 nums：

1. 如果遍历到的 n 大于 d 的末尾元素，则添加进 d 中，继续遍历。
2. 如果遍历到的 n 小于 d 的末尾元素，则在 d 中查找满足 d[i-1]<n<d[i] 的下标 i，更新 d[i]=n。

对于查找下标 i，使用二分查找。 以输入序列 [0,8,4,12,2] 为例： 第一步，插入0，d=[0]; 第二步，插入8，d=[0,8]; 第三步，插入4，d=[0,4]; 第四步，插入12，d=[0,4,12]; 第五步，插入2，d=[0,2,12]。

每次遍历到了一个 n，d 会更新小于等于 n 的最长子序列。

func lenOfLIS2(data []int) int {
	cnt := len(data)
	if cnt < 1 {
		return 0
	}
	// 对于 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，d[i] 关于 i 单调自增
	d := make([]int, 1)
	d[0] = data[0]

	for i := 1; i < cnt; i++ {
		if data[i] > d[len(d)-1] {
			// data[i] 更大
			d = append(d, data[i])
		} else {
			// data[i] 小
			low := 0
			high := len(d) - 1
			target := high
			// 二叉查找出 target 的位置
			for low <= high {
				mid := low + (high-low)/2
				if data[i] < d[mid] {
					// 向左收缩
					high = mid - 1
					target = mid
				} else if data[i] > d[mid] {
					// 向右收缩
					low = mid + 1
				}
			}
			d[target] = data[i]
		}
		fmt.Println(d)
	}
	return len(d)
}

func main() {
	var d1 = []int{}
	// d1,len of lis: 0
	fmt.Println("d1,len of lis:", lenOfLIS2(d1))

	var d2 []int
	// d2,len of lis: 0
	fmt.Println("d2,len of lis:", lenOfLIS2(d2))

	var d3 = []int{2, 1, 5, 3, 6, 4, 8, 9, 7}
	// d3,len of lis: 5
	fmt.Println("d3,len of lis:", lenOfLIS2(d3))

	var d4 = []int{2, 5, 1, 0}
	// d4,len of lis: 2
	fmt.Println("d4,len of lis:", lenOfLIS2(d4))
}

时间复杂度：\(O(nlogn)\)，空间复杂度：\(O(n)\)