首页 > 试题广场 >

排序子序列

[编程题]排序子序列
  • 热度指数：15247 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。


输出描述:
输出一个整数表示牛牛可以将A最少划分为多少段排序子序列
示例1

输入

6
1 2 3 2 2 1

输出

2
算法知识视频讲解
开通博客
头像 星不离月
发表于 2022-10-17 10:15:30
数组中会有3种状态，arr[ i ] > arr[ i + 1 ], arr[ i ] = arr[ i + 1 ], arr[ i ] < arr[ i + 1 ] 因为一组会有多个数据，所以 在 if 内套一个循环 循环结束表示 划分了一个子序列， i ++ ，coun 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 永远听党话
发表于 2022-03-30 11:13:30
链接：https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471 来源：牛客网 题目描述 牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A, 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 小浪_coder
发表于 2022-11-22 23:23:42
两种情况 注：count表示可排序的次数。 1、升序遇到降序 count++； 2、降序遇到升序 count++; 做这种题不要不敢写，想到哪里写到哪里，我就是做题的时候不敢往下写，生怕自己走错方向，然后一直错下去，自己还不知道，就不敢写了，其实大家能读懂题目就已经成功了30%~40%，能坚持写下去 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 阿贝尔的日记
发表于 2022-09-05 22:14:37
1 2 3 3 2 1中的 1 2 3 子序列是递增也是非递减，满足。 3 2 1 是递减的，也是非递增，同样满足。 也就是只要遍历非递减或者非递增，就能逐个排除。 注意while遍历时不要越界，把 i < v.size() 写在前面。 #include <iostream> #i 展开全文
去ta的博客 赞 (0) 回复(3) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 信息技术岗 贪心 区块链 测试开发工程师 2020 大数据开发工程师 数据分析师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
76条回答 28680浏览

热门推荐

通过挑战的用户

相关试题

排序子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号