题目

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

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

示例 1：

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

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：
你能将算法的时间复杂度降低到 O(n*log(n)) 吗?

思路

这道题应该是比较容易想到动规方法的，只是常规的状态方程会是O(n*n)复杂度，不过也很有意义，所以下面代码里也放出来了。只是进阶既然都写出来了，那就得挑战下试试啦~

暂时我其实没有除了动规方法之外的进阶方法，所以这里只分析下是如何想到贪心+二心思路的，权当参考：
1、首先，我的思路就是改良动规方法，动规方法里能看得出来会有一个双层循环来更新dp数组，那如何能够降低这里的复杂度呢？当时是感觉有两种方式

要么是改状态方程，使得dp数组可以保证有序，用二分法降低复杂度；
要么是不改状态方程，但是找到大范围剪枝的方法，从而降低复杂度

2、当时想了下，在现有状态方程下，很难找到剪枝方法，所以主要思考方向就放在了改状态方程上。
那问题就是，如何改能保证有序？
可以试着提一个贪心的假设:

如果我找到一个子序列，它在任意一个位置上的值child[i]，都不大于i+1长度的子序列在末尾位置上的值，那么我们就能够找到一个最长的递增子序列。（详细推论可以参考leetCode上的题解，我这里其实也是先想到思路，然后发现这个思路可行的，结果论证过程看了好久（捂脸。。。）
那状态方程有了，开始编码，具体思路和解释会在代码注释上给出

代码

常规dp，O(n*n)

func lengthOfLIS(nums []int) int {
	if len(nums) <= 1 {
		return len(nums)
	}
	// dp数组含义为dp[i]表示从0到i长度的数组中，递增子序列的最大长度
	dp := make([]int, len(nums))
	n := len(nums) - 1
	dp[0] = 1
	maxLen := 1
	for i := 1; i <= n; i++ {
		dp[i]=1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		maxLen = max(maxLen, dp[i])
	}
	return maxLen
}

贪心dp，O(n*log(n))

func lengthOfLIS(nums []int) int {
	// dp数组含义为dp[i]表示i长度的递增子序列中，最小的末尾值。此状态定义，也决定了dp数组有序。本质是一个贪心的思路，论证可以参考题解
	dp := make([]int, len(nums))
	// 当前dp数组的最大长度，也就是最长子序列长度
	dpLen := 0
	for _, num := range nums {
		i, j := 0, dpLen
		for i < j {
			m := (i + j) / 2
			// 因dp数组在此状态设定下有序，二分找比num小的数
			if dp[m] < num {
				i = m + 1
			} else {
				j = m
			}
		}
		// 退出时，i==j。此时有两种情况，一个是num比现有dp数组中某值小，那就更新dp数组
        // 注意例如更新dp[2]意味着在长度为3的子序列中，位置3的值最小可以为此值，
        // 并非指最长子序列中，位置3的值为此值，
        // 所以此dp方程只是想根据这个设定实现dp本身递增而优化查询
		dp[i] = num
		// 另一个是num比现有dp数组中值都大，那就更新扩展了dp数组长度，所以需要将最大长度更新
        // 当然同时，这个状态下，此是dp数组中的状态又保证了，'确实有这个长度的子序列存在'
		if j == dpLen {
			dpLen++
		}
	}
	return dpLen
}

看到这里了，点个赞点个在看呗！~ 多谢啦！~

半亩房顶

LeetCode-300. 最长递增子序列

题目

思路

代码

常规dp，O(n*n)

贪心dp，O(n*log(n))

LeetCode-23. 合并 K 个升序链表