Longest Increasing Subsequence

应用

从下面的例子也可以看出来了，对于什么时候使用LIS的DP算法，答案就是

• 首先我们要找的是subsequence而不是subarray（如果是subarray请出门左转到subarray maximum/subarray sum equals k/subarray range query章节）。
• 其次就是我们要找的sequence／或者说result sequence里相邻的两个数满足一定的逻辑关系，比如increasing, 比如wiggle，比如divisible。只有这样我们才可以建立出来状态转移方程。

另外一道青蛙过河的问题也告诉我们更general的LIS DP定义思想。如果我们想要使用DP，并且还需要比较当前step和上一step的关系。这里指的上一step是指严格意义上的上一步（必须取到）。所以对于青蛙过河问题我们的dp[i]定义就是恰好跳到第ith点时上一步花了多少步。注意这里当前ith点必须得取到，这和LIS问题的定义非常像。

状态定义和状态转移

定义：一般我们需要一个DP数组，dp[i]表示的是以当前ith element作为结尾的subsequence最长是多少。注意这个定义和一般的DP定义都不一样，因为这里dp[i]表示我们一定要取到第i个数。

状态转移方程：拿LIS问题举例，如果nums[i] > nums[j], 那么dp[i] = Math.max(dp[i], dp[j] + 1)

题目

• Leetcode 354. Russian Doll Envelopes (套了LIS马甲的问题）
• Leetcode 300. Longest Increasing Subsequence (基础版，使用binary search，list存储的是针对当前index长度的LIS tail number)
• Leetcode 368. Largest Divisible Subset (又一道套了LIS马甲的问题！！！对于这种数组问题，有时先排个序可能会提供思路)
• Leetcode 376. Wiggle Subsequence (又一道套了LIS马甲的问题，只不过这里我们可以从小大开头，也可以从大小开头，所以我们要用两个dp array分别记录两种状态）