精华内容
下载资源
问答
  • 递增子序列

    2021-04-22 21:33:28
    最长连续递增子序列 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] <...

    最长连续递增子序列

    给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

    连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

    示例 1:

    输入:nums = [1,3,5,4,7]
    输出:3
    解释:最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。
    示例 2:

    输入:nums = [2,2,2,2,2]
    输出:1
    解释:最长连续递增序列是 [2], 长度为1。

    class Solution {
        public int findLengthOfLCIS(int[] nums) {
            int maxLen=0;
            int start=0;
            for(int i=0;i<nums.length;i++){
                if(i>0&&nums[i]<=nums[i-1]){
                    start=i;
                }
                maxLen=Math.max(maxLen,i-start+1);
            }
            return maxLen;
        }
    }
    

    时间复杂度O(n)
    空间复杂度O(1)

    300. 最长递增子序列

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

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

    示例 1:

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

    输入:nums = [0,1,0,3,2,3]
    输出:4
    示例 3:

    输入:nums = [7,7,7,7,7,7,7]
    输出:1

    class Solution {
        public int lengthOfLIS(int[] nums) {
            if(nums.length==0){
                return 0;
            }
            int len=nums.length;
            int[] dp=new int[len];
            //初始化为1,因为一个元素的递增长度为1
            Arrays.fill(dp,1);
            int res=0;
            for(int i=0;i<len;i++){
                for(int j=0;j<i;j++){
                    if(nums[j]<nums[i]){
                        dp[i]=Math.max(dp[i],dp[j]+1);
                    }
                    
                }
                res=Math.max(res,dp[i]);
            }
            return res;
    
    
        }
    }
    

    时间复杂度O(n^2)
    空间复杂度O(n)

    展开全文
  • 文章目录求连续递增子序列(入门级别dp)求最长递增子序列(进阶) 求连续递增子序列(入门级别dp) 与最长递增子序列的共同点在于: 答案在任意子序列中,只是这个是在连续子序列中。 DP[i]的意义相同,都是表示以nums[i...

    求连续递增子序列(入门级别dp)

    与最长递增子序列的共同点在于:
    答案在任意子序列中,只是这个是在连续子序列中。
    DP[i]的意义相同,都是表示以nums[i]为结尾的最长~

    class Solution {
    public:
        int findLengthOfLCIS(vector<int>& nums) {
            if(nums.size()==0)
                return 0;
            int pre = 1;
            int cur ;
            int res = 1;
            for(int i =1;i<nums.size();i++){
                if(nums[i]>nums[i-1])
                    cur = pre+1;
                else
                    cur = 1;
                pre = cur;
                res = max(res,cur);
            }
            return res;
        }
    };
    

    求最长递增子序列(进阶)

    这个DP解效率极其低下。。大家懂了后可以看看其他方法。当然还让我懂得了C++中快速求数组中最大值的方法,可看后面两段代码的效率对比图。

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            if(nums.empty())
                return 0;
            vector<int>dp(nums.size(),1);
            int res = 1;
    //要清楚这种动态规划中dp[i]所代表的是扫描含义,比如这题dp[i]代表的应该是以nums[i]结尾的最长递增子序列。  
           for(int i=1;i<nums.size();i++){
               //搜寻前面比它小的序列结果,而后拼接上去。
               for(int j=i-1;j>=0;j--){
                   if(nums[i]>nums[j])
                        dp[i]=max(dp[j]+1,dp[i]);
                    res = max(dp[i],res);
               }
           }
           //注意这种某某求最长的DP一般都不清楚最后求出的最长子序列在哪个(n)中
           return res;
        }
    };
    

    在这里插入图片描述

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            vector<int>dp(nums.size(),1);
    
           for(int i=1;i<nums.size();i++){
               for(int j=i-1;j>=0;j--){
                   if(nums[i]>nums[j])
                        dp[i]=max(dp[j]+1,dp[i]);
               }
           }
           //注意这种某某求最长的DP一般都不清楚最后求出的最长子序列在哪个(n)中
           return *max_element(dp.begin(),dp.end());
        }
    };
    

    在这里插入图片描述

    展开全文
  • 最长递增子序列算法尚有缺陷,不能输出所有最长递增子序列 最长递增子序列: #include<iostream> using namespace std; void PrintMaxSubSeq(int flag, int i, int *a, int *prev) { if (prev[i] == i) { ...

    最长递增子序列算法尚有缺陷,不能输出所有最长递增子序列

    最长递增子序列:

    #include<iostream>
    using namespace std;
    void PrintMaxSubSeq(int flag, int i, int *a, int *prev)
    {
    	if (prev[i] == i) { cout << a[i] << " "; return; }
    	PrintMaxSubSeq(1, prev[i], a, prev);
    	cout << a[i] << " ";
    	if (0 == flag)cout << endl; //是否是第一次进栈
    }
    int main()
    {
    	int a[10] = { 7,8,9,5,1,2,3,10,11,12 }; //随便写个数组,此处不做用户输入了
    	int count[10]; //标记以当前数字为末尾的最长子序列长度
    	int prev[10]; //标记以当前数字为末尾的最长子序列倒数第二个数字序号
    	int maxx = 0;
    	for (int i = 0; i < 10; i++)
    	{
    		count[i] = 1;
    		prev[i] = i;
    		for (int j = 0; j < i; j++)
    		{
    			if (a[i] > a[j] && count[i] < count[j] + 1)
    			{
    				count[i] = count[j] + 1;
    				prev[i] = j;
    				maxx = maxx < count[i] ? count[i] : maxx;
    			}
    		}
    	}
    	for (int i = 0; i < 10; i++)
    	{
    		if (maxx == count[i])
    		{
    			PrintMaxSubSeq(0, i, a, prev);
                            break;
    		}
    	}
    	return 0;
    }
    
    

    最长连续递增子序列:

    #include<iostream>
    using namespace std;
    void PrintMaxSubSeq(int flag, int i, int *a, int *prev)
    {
    	if (prev[i] == i) { cout << a[i] << " "; return; }
    	PrintMaxSubSeq(1, prev[i], a, prev);
    	cout << a[i] << " ";
    	if (0 == flag)cout << endl; //是否是第一次进栈
    }
    int main()
    {
    	int a[10] = { 10,11,12,9,8,7,6,1,2,3 }; //随便写个数组,此处不做用户输入了
    	int count[10]; //标记以当前数字为末尾的最长子序列长度
    	int prev[10]; //标记以当前数字为末尾的最长子序列倒数第二个数字序号
    	int maxx = 0;
    	count[0] = 1;
    	prev[0] = 0;
    	for (int i = 1; i < 10; i++)
    	{
    		count[i] = 1;
    		prev[i] = i;
    		if (a[i] > a[i-1] && count[i] < count[i-1] + 1)
    		{
    			count[i] = count[i-1] + 1;
    			prev[i] = i - 1;
    			maxx = maxx < count[i] ? count[i] : maxx;
    		}
    	}
    	for (int i = 0; i < 10; i++)
    	{
    		if (maxx == count[i])
    		{
    			PrintMaxSubSeq(0, i, a, prev);
    		}
    	}
    	return 0;
    }
    
    

     

    展开全文
  • 1134 最长递增子序列 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)例如:5 1 6 8 2...

    基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题
     收藏
     关注
    给出长度为N的数组,找出这个数组的最长递增子序列。(递增子序列是指,子序列的元素是递增的)
    例如:5 1 6 8 2 4 5 10,最长递增子序列是1 2 4 5 10。
    Input
    第1行:1个数N,N为序列的长度(2 <= N <= 50000)
    第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= S[i] <= 10^9)
    Output
    输出最长递增子序列的长度。
    Input示例
    8
    5
    1
    6
    8
    2
    4
    5
    10
    Output示例
    5

    第一次用的是最原始的版本,但是提交后时间超限。。。

    这个时间复杂度是O(n^2)

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=50005;
    const int INF=0x3f3f3f3f;
    int a[MAXN];
    int dp[MAXN];
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		for(int i=0;i<n;i++)	scanf("%d",&a[i]);
    		int ans=0;
    		for(int i=0;i<n;i++)
    		{
    			dp[i]=1;
    			for(int j=0;j<i;j++)
    				if(a[j]<=a[i])	dp[i]=max(dp[i],dp[j]+1);
    			ans=max(ans,dp[i]);
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

    后来又看了白书,有优化的版本,比着抄了一遍

    这个用的是 lower_bound(),只需要循环一次就好,时间复杂度是O(nlogn);

    代码如下

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=50005;
    const int INF=0x3f3f3f3f;
    int a[MAXN];
    int dp[MAXN];
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		memset(dp,0,sizeof(dp));
    		for(int i=0;i<n;i++)	scanf("%d",&a[i]);
    		int ans=0;
    		memset(dp,0x3f,sizeof(dp));
    		fill(dp,dp+n,INF);		
    		for(int i=0;i<n;i++)
    		{
    			*lower_bound(dp,dp+n,a[i])=a[i];
    		}
    		printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
    	}
    	return 0;
    }
    
    



    展开全文
  • 最长递增子序列 300. Longest Increasing Subsequence (Medium) 题目描述:   给定一个数组,找到它的最长递增子序列 思路分析:   动态规划思想,定义一个数组 dp 存储最长递增子序列的长度,dp[n] 表示以 Sn ...
  • leetcode674. 最长连续递增序列 题目描述: 给定一个未经排序的整数数组,找到... nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 class Solution { publ.
  • 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: ...
  • 最长连续递增子序列长度和最长不连续递增子序列长度 1.最长连续递增子序列 例如:Array[6] = {1,5,2,4,3,8} 其最长连续递增子序列就2,4或3,8,最长长度为2 设数组dp[i],表示以i为结尾的最长连续子序列长度,...
  • 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1...
  • 最长递增子序列 子串Description: 描述: This is one of the most popular dynamic programming problems often used as building block to solve other problems. 这是最流行的动态编程问题之一,通常用作解决...
  • 最长递增子序列(LIS)

    万次阅读 多人点赞 2019-03-12 10:20:54
    ① dp[i] 表示以 i 为结尾的最长子序列长度 ② dp[i] 表示长度为 i 的最长递增子序列末尾的数
  • 1.求最长递增子序列长度 方法一:动态规划O(n2) public static int findLongest2(int[] A) { int n = A.length; int[] f = new int[n];// 用于存放f(i)值; f[0] = 1;// 以第a1为末元素的最长递增子序列...
  • 最长单调递增子序列(DP算法) 题目: 给定一个 nnn 个数组成的数据,设计算法找出其中最长单调递增子序列,要求算法复杂度不超过O(n2)O(n^2)O(n2)。 一、问题分析(模型、算法设计和正确性证明等) ​ 假设已经求...
  • 最长递增子序列-源码

    2021-02-14 15:32:17
    最长递增子序列
  • 一、最长递增子序列(LIS)问题 最长递增子序列(LIS)问题:已知一个序列,找出最长单调递增子序列(不要求连续) 网上只找到计算长度的代码,没有找到输出最长序列的代码,因此只有部分参考价值,此处给出的代码,可以...
  • 最长递增子序列dpProblem: You are given an array of length N. You have to find the longest increasing subsequence. 问题:给您一个长度为N的数组。 您必须找到最长的递增子序列 。 Constraints: 1 <= N &...
  • 最长递增子序列

    2019-09-29 20:05:58
    题目一:最长递增子序列 题目链接:最长递增子序列 给出长度为 N 的数组,找出这个数组的最长递增子序列递增子序列是指,子序列的元素是递增的。 例如:5 1 6 8 2 4 5 10,最长递增子序列是 1 2 4 5 10 AC 代码 ...
  • 对于上面的动态规划以第2个问题为例:最长递增子序列:dp[i]状态:以i为自增序列结尾的最大长度为dp[i];决策:从第i个往前找,找到a[j]<a[i],dp[i]=max(dp[i],dp[j]+1);(dp[j]表示符合条件的i前面的一个以j为...
  • 单调递增子序列

    2019-09-28 04:54:26
    单调子序列包含有单调递增子序列和递减子序列,不失一般性,这里只讨论单调递增子序列。首先,从定义上明确我们的问题。给定序列a1, a2, …, an,如果存在满足下列条件的子序列 ai1<=ai2<=…<=aim, (其中...
  • 递增子序列问题

    2020-04-16 15:53:55
    首先谈下,子串和子序列的区别,子串指必须是连续,子序列可以不连续,但是不能改变相对位置。本文所有的问题都是针对于...给定一个整型数组, 你的任务是找到所有该数组的递增子序列递增子序列的长度至少是2。 示...
  • 给定一个数组,就数组最长递增子序列(子序列可以不连续) 2.解法 非常经典的动态规划问题,算法的时间复杂为O(n^2),空间复杂度为O(n)。 关键是结果数组dp[i]怎么计算呢? 每次遍历所有j<i中数组的元素,判断array...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,357
精华内容 3,742
关键字:

递增子序列