lintcode76. 最长上升子序列动态规划

灰太狼 2023-07-03 08:17 47阅读 0赞

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

样例
    样例 1:
    	输入:  [5,4,1,2,3]
    	输出:  3
    	
    	解释:
    	LIS 是 [1,2,3]
    
    
    样例 2:
    	输入: [4,2,4,5,3,7]
    	输出:  4
    	
    	解释: 
    	LIS 是 [2,4,5,7]
    挑战
    要求时间复杂度为O(n^2) 或者 O(nlogn)
    
    说明
    最长上升子序列的定义：
    
    最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。

class Solution {
        
    public:
        /**
         * @param nums: An integer array
         * @return: The length of LIS (longest increasing subsequence)
         */
        int longestIncreasingSubsequence(vector<int> &nums) {
        
            // write your code here
            if(nums.size()==0) return 0;
            vector<int>count(nums.size(),0);
            int res=1;
            count[0]=1;
            for (int i = 1; i < nums.size(); i++) {
        
                /* code */
                int tmp=1;
                for (int j = 0; j < i; j++) {
        
                    /* code */
                    if(nums[i]>nums[j]&&count[j]>=tmp) {
        tmp=count[j]+1;}
                    if(tmp>res) res=tmp;
                    count[i]=tmp;
                }
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode动态规划子序列问题——300.最长上升子序列

题目描述： [300. 最长递增子序列![icon-default.png?t=M4AD][icon-default.png_t_M4AD]https://leetcod

ゝ一世哀愁。/ 2023年10月03日 19:13/ 0 赞/ 57 阅读

相关 leetcode 最长上升子序列动态规划

> 给定一个无序的整数数组，找到其中最长上升子序列的长度。 > 示例: > 输入: \[10,9,2,5,3,7,101,18\] > 输出: 4 > 解释: 最长

梦里梦外;/ 2023年08月17日 15:43/ 0 赞/ 138 阅读

相关 lintcode76. 最长上升子序列动态规划

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。样例样例 1: 输入: [5,4,1,2,3] 输出: 3

灰太狼/ 2023年07月03日 08:17/ 0 赞/ 48 阅读

相关动态规划---最长上升子序列（不连续）

比如序列（1，7，3，5，9，4，8），它的最长上升序列是（1，3，4，8），所以它的最长上升序列长度为 4，那么给定任意长度的序列，请求出它的最长上升序列长度代码：

刺骨的言语ヽ痛彻心扉/ 2023年06月24日 11:26/ 0 赞/ 48 阅读

相关 673 最长递增子序列的个数（动态规划-最长上升子序列）

1. 问题描述：给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1: 输入: \[1,3,5,4,7\] 输出: 2 解释: 有两个最长递增子序列，

雨点打透心脏的1/2处/ 2022年09月02日 12:51/ 0 赞/ 223 阅读

相关【算法】动态规划最长上升子序列

/ 找出最长上升子序列的个数并输出一个最长子序列 / include <stdio.h> define MAX_

ゝ一纸荒年。/ 2022年08月26日 03:43/ 0 赞/ 235 阅读

相关最长上升子序列——动态规划

Think: 1递推思想反向推演递推关系1： b\[i\] = 1//i == 1 || Vi, max(b\[i\], b\[j+1\]) = 0; b\[

港控/mmm°/ 2022年06月17日 03:48/ 0 赞/ 253 阅读

相关 HDU 1160(动态规划-最长上升子序列)

问题描述： FatMouse believes that the fatter a mouse is, the faster it runs. To disprove thi

谁借莪１个温暖的怀抱￠/ 2022年06月03日 07:07/ 0 赞/ 232 阅读

相关动态规划：最长上升子序列

1.1 朴素方法 O（n ^2）: 思路：每个数都遍历他前面的所有数，如果这个数比前面的数要大，更新他自己或者他前面的数+1的最大的一个数。 include<ios

╰半橙微兮°/ 2022年01月22日 09:23/ 0 赞/ 280 阅读

相关动态规划-最长上升子序列LIS

文章目录问题描述一.简单推论（非0 n情况） 1.问题分析 2.状态转移方程 3.参考代码 4

￡神魔★判官ぃ/ 2021年09月07日 06:03/ 0 赞/ 460 阅读