【动态规划】【leetcode】【中等】300. 最长递增子序列_给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列是由数组派生-程序员宅基地

题目：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

原题地址：

300. 最长递增子序列

解题思路：

定义一个数组dp，dp[i]表示以nums[i]结尾的子序列的长度，则dp[i+1]的值就是[0, i]之间小于nums[i+1]的dp最大值+1，如果没有满足条件的，则dp[i+1] = 1。

例如，

以7结尾的子序列：

7前面小于7的数字有3个，分别是2,5,3，7可以与他们分别组成子序列，分别是[,,,2,7], [,,,5,7], [,,,3,7]，新的子序列长度分别是2,3,3，7对应下标是5，则dp[5]=3。

同理，以101结尾的子序列：

101前面小于101的数字有6个，分别是10,9,2,5,3,7，新的子序列长度分别是2,2,2,3,3,4，则dp[6]=max(2,2,2,3,3,4)。

c代码如下：

int lengthOfLIS(int* nums, int numsSize){
    if (numsSize == 0) return 0;
    int dp[2501] = {0}; // dp[i]表示必须以nums[i]结尾的子序列的长度
    dp[0] = 1;
    for (int i = 1; i < numsSize; i++) {
        int max = 0;
        for (int k = 0; k < i; k++) {
            if (nums[k] < nums[i] && max < dp[k]) {
                max = dp[k];
            }
        }
        dp[i] = max + 1;
    }
    int max = dp[0];
    for (int i = 0; i < numsSize; i++) {
        if (max < dp[i]) max = dp[i];
    }
    return max;
}

本文链接：https://blog.csdn.net/hbuxiaoshe/article/details/114376014

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

[论文速度] 超分系列：基于频率分离的图像超分辨率算法两篇 ICCVW 2019 和 CVPRW 2020_frequency separation for real-world super-resoluti-程序员宅基地

文章浏览阅读2.9k次。Frequency Separation for Real-World Super-Resolution[PAPER]_frequency separation for real-world super-resolution

查看vmware虚拟机是否能上网及虚拟机的网卡配置_怎么看虚拟机有没有连接到网络-程序员宅基地

文章浏览阅读6.7k次。本文主要讲述如何使用命令查看虚拟机是否能够联网，及虚拟机的网卡配置。本文主要介绍，如何查看虚拟机网卡，及测试上网功能。_怎么看虚拟机有没有连接到网络

详解SaaS产品的5类核心指标-程序员宅基地

文章浏览阅读3.2k次。导读：在SaaS的经营中，对数据的整理和分析可以帮助我们有效地了解企业经营现状和可能存在的发展机遇。对于企业的不同角色和不同发展阶段，其需要关注的数据指标会有所不同。下面我将根据自己多年从..._支付产品核心指标

Linux C++ 获取某一进程的CPU占用率以及内存占用情况_c++统计当前进程内存占用-程序员宅基地

文章浏览阅读4.8k次。#include #include #include #include #include #define VMRSS_LINE 17#define VMSIZE_LINE 13#define PROCESS_ITEM 14typedef struct { unsigned long user; unsigned long nice; unsigned long syste_c++统计当前进程内存占用

display 命令全集_display命令-程序员宅基地

文章浏览阅读1.1k次。查看静态路由表的目的地址以及下一跳的ip地址拿掉任何配置的命令前面加undo XXXXXXXX查看rip协议：ospf 配置查看命令_display命令

计算机硕博连读最快几年,“硕博连读”到底是不是一个坑？-程序员宅基地

文章浏览阅读2.4k次。原标题：“硕博连读”到底是不是一个坑？近年来“硕博连读”四个字的热度是越来越高，很显然硕士学历的身价再一次开始下降，大家都纷纷开始考虑要不要读博了，很多研究生导师也会在学生研一或研二结束时问其要不要硕博连读，有些导师不但问，还会劝：小杨呀，我看你平时科研能力还不错，要不要硕博连读，就不用再参加考试了，直接攻读博士，5年就可以毕业，多省事儿…… 差点就心动了！到底什么是“硕博连读”呢？其实就和本硕连..._本硕博计算机类连读怎么样亏吗