原题
300. Longest Increasing Subsequence
本题一共有两种解决思路，首先是动态规划，想法和思路比较简单，复杂度为$O(n^2)$。另一种就是结合了贪心思想的二分查找，这种方法比较难以想到，但是复杂度更低，只有$O(n\log n)$。
动态规划思路
我们用dp[i]表示以nums[i]作为结尾的最长上升子序列的长度。那么，边界条件就是dp[0]=1，且每个dp[i]最小为1（即每个数字本身就构成了一个上升子序列）。状态转移方程的话，则是要考虑i之前的$j\in[0,i-1]$，通过比较nums[i]和nums[j]的大小来确定i处能够产生的最长上升子序列，如果nums[i]更小的话，显然是没有办法继承dp[j]的状态的；如果nums[i]更大的话，就可以尝试用dp[j]来更新dp[i]。因此状态转移方程可以表示为
\(dp[i] = max(dp[i], dp[j]+1)\quad j<i \quad nums[i]>nums[j]\)
既然dp[i]表示的是以nums[i]结尾的最长上升子序列的长度，我们不能保证最长的子序列是以哪个数字结尾的，所以最后的答案表示是$max(dp[i]), i\in [1,n-1]$。
动态规划代码
func lengthOfLIS(nums []int) int {
// 动态规划
n := len(nums)
// 边界处理
if n == 0 {
return 0
}
dp := make([]int, n)
ans := 0
// 动态规划过程
for i := 0; 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)
}
}
// 答案表示
ans = max(dp[i], ans)
}
return ans
}
贪心+二分思路
根据最长上升子序列的定义，我们会想到，要让子序列里的每个数字都尽可能小，从而才能增大长度延续下去的可能。那么我们便想到维护一个数组f[i]，表示长度为i+1的上升子序列的末尾最小值。
这里也用到了动态规划优化的一个技巧，那就是交换状态和状态值。比较dp[i]和f[i]的定义：
dp[i]表示末尾元素为nums[i]的LIS的长度
f[i]表示长度为i+1的LIS的末尾元素的最小值
可以发现这种优化正是采用了这一技巧从而得以将贪心和二分的思想利用起来。
具体来说，对于新的nums[j]，二分查找其在f中的位置，找到首个大于nums[j]的元素x，然后用nums[j]取代x，如果说找不到(二分查找返回了f的末位)，那么就将nums[j]拼接到f上，最后的答案就是f的长度。
这个贪心为什么可行呢？因为我们要求f作为LIS必须是严格递增的，那么相应的我们是希望f中数字的增长速度应该是相对更慢的，那样的话可以容纳更多的数字，因此，每次只进行一个数字的替换，并不会影响答案的正确性，因为这种替换可以看作是一种”尝试”，并不会真的影响我们目前确定的LIS长度的正确性。比方说[1,3,5,2,0,7,4]这个数组，最替换完成后应该是[0,2,4,7]，正确答案应该是[1,3,5,7]，但是这样并不影响LIS长度的正确性，因为这种替换不会影响已有的长度，只会让未来得到更长序列的可能性增加。
贪心+二分代码
func lengthOfLIS(nums []int) int {
// 贪心+二分
f := []int{}
n := len(nums)
for i := 0; i < n; i++ {
idx := binarySearch(f, nums[i])
if idx == len(f) {
// 找不到比nums[i]更大的值
f = append(f, nums[i])
} else {
f[idx] = nums[i]
}
}
return len(f)
}
func binarySearch(nums []int, x int) int {
l := 0
r := len(nums)
for l < r {
mid := (l+r) >> 1
if nums[mid] < x {
l = mid+1
} else {
r = mid
}
}
// l是第一个大于等于x的值索引
return l
}
