Menu Close

动态规划解最长子序列子串等一类问题之最长上升子序列[Thorold’s Deer]

一些名词

  • 最长上升子序列(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]这样的结果,这时候ji不能形成递增,i结尾的子序列所形成的最长子序列的长度等价于以j结尾的子序列所形成的最长子序列的长度,即dp[i]=dp[j]
    • nums[i]>nums[j],说明j处的值小于i处值,形成的子序列是nums[0...j,i]这样的结果,这时候从ji是递增的,这时候需要在长度上+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<inums[i]<=nums[j]时,表示以j结束的子序列和i结束的子序列不能形成上升子序列,举 例:[1,4,5,7,6,8],当iindex4的位置,也就是nums[i] =6 ,j index3时,nums[j] =7 ,以nums[j] nums[i] 不能形成一个上升子序列

边界条件

  • nums[0...i]只有一个元素时,即以这一个元素结尾的子序列,最长上升子序列是其自身,为1

核心代码

方法1:DP

方法2:贪心+二分

  • 准备一个辅助数组tails,其中tails[i]表示长度为i+1nums[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],这与一开始假设的条件矛盾,假设条件不成立

关联阅读

发表评论

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

苏ICP备20029284号-1