美文网首页
最长递增子序列

最长递增子序列

作者: simon_kin | 来源:发表于2021-01-27 15:05 被阅读0次

最长递增子序列(Longest Increasing Subsequence,简写 LIS)是动态规划
比较经典的一个问题。

先定义一个dp 数组:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
最终结果(子序列的最大长度)就是 dp 数组中的最大值。

根据刚才对 dp 数组的定义,dp[i] 的值,也就是以 nums[i] 为结尾的最长递增子序列。

如何通过 dp[0...i-] 的结果推出dp[i]
既然是递增子序列,我们只要找到前面那些结尾比 nums[i]小的子序列,然后把 nums[i] 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一。这里可能出现多个取最大那个。

base case。dp 数组应该全部初始化为 1

public static int[] lis(int[] nums){
    int length = nums.length;
    int[] dp = new int[length];
    for (int i=0;i<length;i++) {
        dp[i] = 1;
        for (int j=0;j<i;j++) {
            if (nums[j]<nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp;
}

相关文章

  • LeetCode-300-最长递增子序列

    LeetCode-300-最长递增子序列 300. 最长递增子序列[https://leetcode-cn.com...

  • 动态规划-LIS

    LIS 最长递增子序列 如 x 的 最长递增子序列长度为5 方法一 对 x 排序(升序)生成 x_sorted 对...

  • LeetCode 300. Longest Increasing

    问题描述 给定一个未排序的整数数组,找出最长的递增子序列。 栗子: 注意: 可能存在多种最长递增子序列的组合,只需...

  • 最长递增子序列

    问题描述 求最长递增子序列的长度 分析 主要是确定状态,F[i]表示以ai 结束的最长递增子序列长度,F[i]=m...

  • 经典DP问题合集

    一、上台阶问题 二、矩阵最小路径和 三、最长递增子序列 四、最长公共子序列 五、背包问题

  • 动态规划常见面试题

    子序列类型编辑距离 最长递增子序列 最大子数组 最长公共子序列 背包问题0-1背包问题 子集背包问题 完全背包问题...

  • 最长递增子序列: 动态规划和LCS(最长公共子序列)

    最长递增子序列: 动态规划和LCS(最长公共子序列)子序列和子串的区别:子序列不连续,字串连续。这个题两种解法 动...

  • 最长递增子序列

    //Given an unsorted array of integers, find the length of...

  • 最长递增子序列

    通常有4个步骤来设计动态规划算法: 1.刻画一个最优解的结构特征。 2.递归地定义最优解的值。 3.计算最优解的值...

  • 最长递增子序列

    问题定义: 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度...

网友评论

      本文标题:最长递增子序列

      本文链接:https://www.haomeiwen.com/subject/etrazktx.html