Menu Close

动态规划解最长子序列子串等一类问题之最长连续递增序列[Reindeer]

0.png

一些名词

  • 最长上升子序列(LIS):Longest Increasing Subsequence
  • 最长连续序列(LCS):Longest Consecutive Sequence
  • 最长连续递增序列(LCIS):Longest Continuous Increasing Subsequence
  • 最长公共子序列(LCS):Longest Common Subsequence

子串与子序列区别:子串不可跳跃,子序列可以跳跃,如 “AC”是“ABCDEFG”的子序列,而不是子串。 而“ABC”则是其子串

1.最长连续递增序列

1590505325894.png

题目要求最长连续递增序列,序列本身可以跳跃,但是题意要求连续,也即是不可跳跃

定义状态

  • 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))

方法2:DP(O(1))

  • 因为只会依赖于ii-1这两个状态,借助一个常数的级别的一维数组dp[2],辅以奇偶数的小技巧

2.最长递增子序列的个数

1590505435058.png

与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]的组合方式

673_leetcode-1590626196059.jpg

整体代码

复杂度分析

  • 时间复杂度O(N^2),两个for loop
  • 空间复杂度:O(N)dpcounter数组长度N

推荐阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1