C++最长上升子序列

C++最长上升子序列现有数列a1,a2,a3……aN。在其中找到严格递增序列ai1,ai2,ai3,……aiK(1<=i1

大家好,又见面了,我是你们的朋友全栈君。

最长上升子序列简介

题目描述
现有数列a1,a2,a3……aN。在其中找到严格递增序列ai1,ai2,ai3,……aiK(1 <= i1 < i2 < i3 < …… < iK <= N),请找出序列a的最长上升子序列的长度,既K的最大值。

输入格式
第一行:一个整数N。
第二行:N个整数a1,a2,a3……aN。

输出格式
一行,最大的K。

输入样例

10
5 10 8 9 7 10 13 12 25 13

输出样例

6

二维动态规划解法

提到DP,就一定就要去想:状态、转移方程、初值和答案了。

  1. 状态:dp[i]指在1~i这i个数中,必须包含a[i]这个数的最长上升子序列。
  2. 转移方程:if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1)(1 <= j <= i – 1)
    其实这个的意思就是:如果说在1~(i – 1)这(i – 1)个数中,a[j] < a[i],a[i]就可以接上a[j],形成一个比dp[j]又多了1的递增序列,因此每次判断并取最大值就行了。
  3. 初值:dp[i] = 1(一个数本身就是一个递增序列)。
  4. 答案:max{dp[i]}

(PS:NR指序列长度的上限)

# include <cstdio>
# include <iostream> 
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

# define FOR(i, a, b) for(int i = a; i <= b; i++)
# define _FOR(i, a, b) for(int i = a; i >= b; i--)

const int NR = 100000;

int n, ans;
int a[NR + 2], dp[NR + 2];

int main()
{ 
   
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n) dp[i] = 1;
    FOR(i, 2, n){ 
   
        FOR(j, 1, i - 1)
            if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

贪心二分查找解法

二维动态规划的时间复杂度为On^2,太多了,我们想去优化,可是我们发现直接在二维上改好像改不了,没办法,只好再想一个新的方法了。

这次,我们开一个新的数组f,f[i]表示当上升子序列长度为i时,此子序列最后一个元素的最小值。我们会发现这个f数组是随着i值的增加,f[i]不断增大的单调队列。因为如果长度为i的上升子序列最后一位都为f[i]了,那长度(i + 1)的最后一位至少也得是f[i] + 1了吧。

这样我们从1到n一个元素一个元素的分析,当到了第i个元素时,我们在f数组中找第一个大于等于a[i]的f[k],这就代表长度为(k – 1)的上升子序列最后一位的最少值是f数组中最后一个小于a[i]的数,所以就让我们就可以把a[i]放到长度为(k – 1)的这个上升子序列的后面,形成一个新的长度为k的这个上升子序列,接下来更新f[k]的值f[k] = min(f[k], a[i])可我们发现我们找f[k]时就说了f[k]是f数组中第一个大于等于a[i]的数,所以直接f[k] = a[i]就好了。

下图仅供参考。
在这里插入图片描述
其中,在f数组中找第一个大于等于a[i]的f[k]时,可以用到二分查找函数中的lower_bound函数。

如果你还没有学过lower_bound可以到此网站学习lower_bound函数的用法
https://blog.csdn.net/SkeletonKing233/article/details/99479707

这样时间复杂度就从On^2降到了Onlogn,大大减少了时间的消耗。

以下为代码:

# include <cstdio>
# include <iostream> 
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

# define FOR(i, a, b) for(int i = a; i <= b; i++)
# define _FOR(i, a, b) for(int i = a; i >= b; i--)

const int NR = 100000;

int n, ans;
int a[NR + 2];
int f[NR + 2];

int main()
{ 
   
	scanf("%d", &n);
 	FOR(i, 1, n) scanf("%d", &a[i]);
 	f[0] = -2e9;
 	FOR(i, 1, n){ 
   
 		int k = lower_bound(f, f + ans + 1, a[i]) - f;
 		f[k] = a[i];
 		ans = max(ans, k);
	}
	printf("%d\n", ans);
	return 0;
}

最长下降、不上升、不下降子序列

剩下的这三种都与第一种十分相像:

  • 最长不下降子序列:就是把FOR循环中的lower_bound函数改成upper_bound函数。
  • 最长下降子序列:就是把FOR循环前的f[0] = -2e9改成f[0] = 2e9之后再在全局写一个比较函数cmp,并在lower_bound函数中做为第4个参数引用
  • 最长不上升子序列:就是先改成最长下降子序列,之后再把FOR循环中的lower_bound函数改成upper_bound函数。

PS:cmp函数的写法:

bool cmp(int x, int y){ 
   
	return x > y;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/131509.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 虚拟机怎么安装vmware tools

    虚拟机怎么安装vmware tools这篇文章主要为大家详细介绍了VMwareWorkstation12安装Ubuntu和VMwareTools教程,具有一定的参考价值,感兴趣的小伙伴们可以参考一下之前我通过百度经验上的过程来安装Ubuntu16,但是每次安装的时候没有什么问题,就是安装好了Tools,也设置好了共享文件夹,但是在路径:/mnt/hgfs下每次都找不到共享文件夹。后来我研究了好久,应该是安装的时候…

  • 三点估算法怎么计算_比例估算法公式

    三点估算法怎么计算_比例估算法公式某公司接到一栋大楼的布线任务,经过分析决定将大楼的四层布线任务分别交给甲、乙、丙、丁四个项目经理,每人负责一层布线任务,每层面积为10000平米。布线任务由同一个施工队施工,该工程队有5个施工组。甲经过测算,预计每个施工组每天可以铺设完成200平米,于是估计任务完成时间为10天,甲带领施工队最终经过14天完成任务;乙在施工前咨询了工程队中有经验的成员,经过分析之后估算时间为12天,乙带领施工队最终…

    2022年10月30日
  • 推荐几个JAVA 学习不错的网站

    推荐几个JAVA 学习不错的网站  学习Java呢!不仅经是靠的自身的努力,还要懂得他的规范,所以要多看一些Java技术文档:    我感觉有五个Java自学网站不错推荐一下子;    这些网站可以提供一些最新Java的资料;    有时定期开设讲座等线下活动;    而且里面的一些Java相关的问题以及讨论;    不仅适用于Java小白程序员,而且还适用于一些Java大神;    其实外网有很多比较专业的Java学习网站,但是鉴于为Java小白推荐网站,立足当下!!!  

  • WinExec

    WinExecWinAPI:WinExec-运行外部程序//声明WinExec(lpCmdLine:LPCSTR;{文件名和参数;如没指定路径会按以下顺序查找:程序目录/当前目录/System32/

  • mysql性能优化-慢查询分析、优化索引和配置

    mysql性能优化-慢查询分析、优化索引和配置

  • 32位int取值范围_正则表达式判断是否是int32

    32位int取值范围_正则表达式判断是否是int32在做游戏的开发中,由于游戏运行的时间已经很长,数据量

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号