一些名词
- 最长上升子序列(
LIS
):Longest Increasing Subsequence
- 最长连续序列(
LCS
):Longest Consecutive Sequence
- 最长连续递增序列(
LCIS
):Longest Continuous Increasing Subsequence
- 最长公共子序列(
LCS
):Longest Common Subsequence
子串与子序列区别:子串不可跳跃,子序列可以跳跃,如 “AC”是“ABCDEFG”的子序列,而不是子串。 而“ABC”则是其子串
1.最长连续递增序列
题目要求最长连续递增序列,序列本身可以跳跃,但是题意要求连续,也即是不可跳跃
定义状态
-
dp[i]
表示以i
位置结尾,即nums[i]
值结尾的,最长连续递增序列的长度 -
只要关注当前位置
i
与其前一个的位置i-1
的值的大小:nums[i]>nums[i-1]
,i
至少可以与i-1
形成一个连续递增序列,因为它们俩挨着,并且是递增的,长度上是dp[i-1]+1
nums[i]<=nums[i-1]
,这时候,不能形成连续递增序列,后一个数要比前一个数小,呈下降的趋势,注意=
不认为是递增的
方法1:DP(O(N)
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1);//至少可以与其自身形成递增序列 int max = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1; max = Math.max(max, dp[i]); } } return max; } |
方法2:DP(O(1)
)
- 因为只会依赖于
i
与i-1
这两个状态,借助一个常数的级别的一维数组dp[2]
,辅以奇偶数的小技巧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; int max = 1; int[] dp = new int[2]; dp[0] = 1; for (int i = 1; i < n; i++) { dp[i % 2] = 1;//前一个状态值都会被覆盖,需要重新初始化 if (nums[i] > nums[i - 1]) { dp[i % 2] += dp[(i - 1) % 2];//当前状态依赖前一状态,需要再前一状态上累加 } max = Math.max(max, dp[i % 2]); } return max; } |
2.最长递增子序列的个数
与300题主体类似,本题的难点是记录下组合的方式
定义状态
-
dp[i]
表示以i
位置结尾,即nums[i]
值结尾的,最长连续递增序列的长度 -
dp
初始化为1,因为nums[i]
自身可以形成一个长度为1的最长递增序列 -
遍历
[0...i]
,再套一层[0...j]
,其中j<i
- 当
nums[j]<nums[i]
,说明以[...j,i]
这段可以形成最长递增序列,长度是dp[j]+1
,其中dp[j]
是以j
为结尾的最长递增序列的长度 - 当
nums[j]≥nums[i]
,以[...j,i]
是不能形成最长递增序列的,为dp[i]
,其被初始化为1了
- 当
-
接下来要统计最长递增序列的个数,准备长度
n
的数组counter
,定义count[i]
为以nums[i]
结尾的最长递增子序列的组合数量,这其中有两个限定条件,一是以nums[i]
结尾,二是最长递增子序列,不是最长的不是这个counter
数组考虑的,举例,1,2,4,3,5,4,7,2
,最长递增序列有1,2,4,5,7;1,2,3,5,7;1,2,3,4,7
三种情况,以nums[6]=7
结尾的counter[6]=3
-
下面是如何生成这个
counter
数组:- 总体要满足
nums[i] > nums[j]
,才有意义,这样可以形成递增序列 - 当
dp[j] + 1>dp[i]
,说明第一次找到以nums[i]
为结尾的最长递增子序列,长度为dp[j] + 1
,进而可以推出counter[i] = counter[j]
, 以nums[i]
结尾的最长递增子序列的组合数=以nums[j]
结尾的最长递增子序列的组合数,这个可以这么理解:当[...j]
形成的组合数是值的话,其每一种组合结尾补上[i]
,即[...j,i]
,对于组合数本身是没有增加的,还是A
值,唯独只是递增子序列的长度+1
了 - 当
dp[j] + 1=dp[i]
,说明这个长度已经找到过一次了,counter[i] += counter[j]
,现在的组合方式+counter[j]
的组合方式
- 总体要满足
整体代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public int findNumberOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int n = nums.length; int[] dp = new int[n]; int[] counter = new int[n]; Arrays.fill(dp, 1); Arrays.fill(counter, 1); int max = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { if (dp[j] + 1 > dp[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); counter[i] = counter[j]; } else if (dp[j] + 1 == dp[i]) { counter[i] += counter[j]; } } } max = Math.max(max, dp[i]); } int res = 0; for (int i = 0; i < n; i++) { if (dp[i] == max) res += counter[i]; } return res; } |
复杂度分析
- 时间复杂度:
O(N^2)
,两个for loop
- 空间复杂度:
O(N)
,dp
与counter
数组长度N