一些名词
- 最长上升子序列(
LIS):Longest Increasing Subsequence - 最长连续序列(
LCS):Longest Consecutive Sequence - 最长连续递增序列(
LCIS):Longest Continuous Increasing Subsequence - 最长公共子序列(
LCS):Longest Common Subsequence
子串与子序列区别：子串不可跳跃，子序列可以跳跃，如 “AC”是“ABCDEFG”的子序列，而不是子串。 而“ABC”则是其子串
定义状态
dp[i]表示在区间nums[0....i]区间范围内的最长上升子序列的长度
- 比较索引
i与其前面出现的某个位置j的大小- 当
nums[i]<=nums[j]，说明j处的值要比i处的值的，要是形成子序列则是nums[0...j,i]这样的结果，这时候j到i不能形成递增，以i结尾的子序列所形成的最长子序列的长度等价于以j结尾的子序列所形成的最长子序列的长度，即dp[i]=dp[j] - 当
nums[i]>nums[j]，说明j处的值小于i处值，形成的子序列是nums[0...j,i]这样的结果，这时候从j到i是递增的，这时候需要在长度上+1，即dp[i]=dp[j+1] - 取上述两种情况的
max，动态转移方程为：dp[i] = Math.max(dp[i], dp[j] + 1)|0<=j<i<n - 举例：如果遍历到
i位置，在[0-i]区间内有[0-j] j<i当nums[i]<=nums[j]时，表示以j结束的子序列和i结束的子序列不能形成上升子序列，举 例：[1,4,5,7,6,8]，当i在index为4的位置，也就是nums[i] =6,j为index为3时，nums[j] =7,以nums[j]和nums[i]不能形成一个上升子序列
- 当
边界条件
- 当
nums[0...i]只有一个元素时，即以这一个元素结尾的子序列，最长上升子序列是其自身，为1
核心代码
|
1 2 3 4 5 6 7 |
for (int i = 0; i < len; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } |
方法1:DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public int lengthOfLIS(int[] nums) { //dp[i]: 到i为止 (对于所有 j in [0, i], 记录max length of increasing subsequence if (nums == null || nums.length == 0) { return 0; } int len = nums.length; int[] dp = new int[len]; int res = 0; for (int i = 0; i < len; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { //i 位置的数与[0,i]位置之间的数比较，如果大于进逻辑 if (nums[i] > nums[j]) { //等于dp[i]或者dp[j] + 1（j对应的值比i小）的最大值 dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } |
方法2：贪心+二分
- 准备一个辅助数组
tails,其中tails[i]表示长度为i+1即nums[0...i]的序列尾部元素的值 - 辅助数组
tails一定是严格单调递增的，即在nums[0...j..i]区间上，tails[j]<tails[i]，下面使用 反证法证明这个结论- 假设
nums[0...j..i]这个区间上，tails[j]>=tails[i],从i这个子序列向前删除i-j个元素，这时候长度变为j的子序列，这时候的尾部元素的值为x - 根据
tails数组的定义，x<tails[i] - 而
x又是tails[j]的值，即x=tails[j] - 得出
tails[i]>tails[j],这与一开始假设的条件矛盾，假设条件不成立
- 假设
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public int lengthOfLISII(int[] nums) { int n = nums.length; int[] tails = new int[n]; int end = 0; for (int i = 0; i < n; i++) { int l = 0, r = end; while (l < r) { int m = (l + r) / 2; if (tails[m] <= nums[i]) l = m + 1; else r = m; } tails[l] = nums[i]; if (end == r) end++; } return end; } |