• 代码随想录算法训练营 动态规划part13

    一、最长递增子序列 

    300. 最长递增子序列 - 力扣（LeetCode）

    前几天算法课上老师讲了

    状态定义：

    dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。
    转移方程： 设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：

    当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
    当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
    上述所有 1. 情况 下计算出的 dp[j]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)。
    转移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)。
    初始状态：

    dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。
    返回值：

    返回 dp 列表最大值，即可得到全局最长上升子序列长度。

    300. 最长递增子序列 - 力扣（LeetCode）

    1. // Dynamic programming.
    2. class Solution {
    3.     public int lengthOfLIS(int[] nums) {
    4.         if(nums.length == 0) return 0;
    5.         int[] dp = new int[nums.length];
    6.         int res = 0;
    7.         Arrays.fill(dp, 1);
    8.         for(int i = 0; i < nums.length; i++) {
    9.             for(int j = 0; j < i; j++) {
    10.                 if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    11.             }
    12.             res = Math.max(res, dp[i]);
    13.         }
    14.         return res;
    15.     }
    16. }
    17.

    二、最长连续递增序列 

    674. 最长连续递增序列 - 力扣（LeetCode）

    1. class Solution {
    2.     public int findLengthOfLCIS(int[] nums) {
    3.         if(nums.length <= 1)
    4.             return nums.length;
    5.         int ans = 1;
    6.         int count = 1;
    7.         for(int i=0;i<nums.length-1;i++) {
    8.             if(nums[i+1] > nums[i]) {
    9.                 count++;
    10.             } else {  
    11.                 count = 1;
    12.             }
    13.             ans = count > ans ? count : ans;
    14.         }
    15.         return ans;
    16.     }
    17. }
    18.

    三、 最长重复子数组  

    1. class Solution {
    2.     public int findLength(int[] nums1, int[] nums2) {
    3.         return nums1.length<=nums2.length? findMax(nums1,nums2):findMax(nums2,nums1);
    4.     }
    5.  
    6.     public int findMax(int[] nums1, int[] nums2){
    7.         int max=0;
    8.         int m=nums1.length,n=nums2.length;
    9.         /**
    10.         nums1,nums2中较短的数组不动，这里默认nums1，较长的数组滑动
    11.         初始位置：nums2右边界挨着nums1左边界，nums2从左往右滑动
    12.          */
    13.         // 第一阶段：nums2从左往右滑动，两数组重合部分长度不断增加，重合部分长度len从1开始增加
    14.         // 重合部分：nums1起点下标0，nums2起点下标n-len，
    15.         for(int len=1;len<=m;len++){
    16.             max=Math.max(max,maxLen(nums1,0,nums2,n-len,len));
    17.         }
    18.         // 第二阶段：nums2从左往右滑动，两数组重合部分长度不变，重合部分长度始终为nums1长度m
    19.         //  重合部分：nums1起点下标0，nums2起点下标n-m，然后递减
    20.         for(int j=n-m;j>=0;j--){
    21.             max=Math.max(max,maxLen(nums1,0,nums2,j,m));
    22.         }
    23.         // 第三阶段：nums2从左往右滑动，两数组重合部分长度递减，重合部分长度始终为nums1长度m-i
    24.         //  重合部分：nums1起点下标i，递增，nums2起点下标0
    25.         for(int i=1;i<m;i++){
    26.             max=Math.max(max,maxLen(nums1,i,nums2,0,m-i));
    27.         }
    28.         return max;
    29.     }
    30.  
    31.     /**
    32.     nums1中下标i开始，nums2中下标j开始，长度为len子数组中，最长公共子数组(注意要连续)长度
    33.      */
    34.     public int maxLen(int[] nums1,int i,int[] nums2,int j,int len){
    35.         int count=0,res=0;
    36.         for(int k=0;k<len;k++){
    37.             if(nums1[i+k]==nums2[j+k]){
    38.                 count++;
    39.             }else if(count>0){
    40.                 //进入到这个if判断体里面，说明当前 nums1[i+k]!=nums2[j+k],即之前的公共子数组不再连续，
    41.                 // 所以要记录最大值，同时将count置零
    42.                 res=Math.max(count,res);
    43.                 count=0;
    44.             }
    45.         }
    46.         /**
    47.         1，count>0,说明有公共子数组是以nums1[i+len-1],nums2[j+len-1]结尾的，
    48.            上面最后一步for循环没有进入到else if判断题里面，所以最终结果要取当前count和res的最大值
    49.         2，count=0，说明res已经更新过了，res即为最终结果
    50.          */
    51.         return count>0? Math.max(count,res):res;
    52.     }
    53. }

  • 相关阅读:
    线性代数 --- 用几何图形进一步说明高斯消元法
    如何借助现有股票量化交易平台编写策略和回测分析
    Linux环境变量之shell中export定义全局变量和echo 变量的区别
    读懂跨链技术未来可能性：存在哪些机遇及进展？
    python中logging日志模块
    Gitee和Git学习笔记
    斐波那契散列算法和hashMap实践
    【ShardingSphere】水平分库分表配置方法
    快速学会git版本管理——创建分支和合并分支
    Redis持久化实战
  • 原文地址：https://blog.csdn.net/m0_63297917/article/details/133183396