首页 > 试题广场 >

有效序列的数量

[编程题]有效序列的数量
  • 热度指数：1976 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
我们定义一个有效序列为：该序列两端的数一个为最小值，另一个为次小值。（即序列两端以外的数一定大于等于最左边的数且大于等于最右边的数）

现在给你一个序列 a ，想让你找到它的连续子序列中有多少个有效序列(比如 ，1 2 ，2 3，1 2 3 是序列 1 2 3 的连续子序列，但是 1 3 不是)

注：长度为 2 的子序列，一定为有效序列，长度为 1 的子序列，一定不是有效序列

输入描述:
第一行输入一个整数 n 代表这个序列的长度
接下来输入 n 个整数，a[i] 代表系列中第 i 个元素

对于 20% 的数据, 1 ≤ n ≤ 100
对于 70% 的数据, 1 ≤ n ≤ 3,000
对于 100% 的数据, 1 ≤ n ≤ 100,000

对于 100% 的数据, 1 ≤ a[i] ≤ 1,000,000,000


输出描述:
输出一个正整数表示有效序列的数量。
示例1

输入

4
1 3 1 2

输出

4

说明

一共有 4 组有效序列，分别为：
子序列[1,3] 因为长度为 2，一定为有效序列
子序列[1,3,1] 因为第2个数 “3” 大于第 1 个数和第 3 个数
子序列[3,1] 因为长度为 2，一定为有效序列
子序列[1,2] 因为长度为 2，一定为有效序列
示例2

输入

4
1 1 2 1

输出

5

说明

一共有6个长度不小于2的连续子序列，除了[1,1,2]以外，其他5个都是有效子序列
示例3

输入

7
1 4 2 5 7 1 3

输出

10

说明

一共有10组，分别为：
[1,4], [1,4,2], [1,4,2,5,7,1], [4,2], [2,5], [2,5,7,1], [5,7], [5,7,1], [7,1], [1,3]
算法知识视频讲解
开通博客
头像 J_song
发表于 2022-04-20 00:56:36
">using namespace std; int main() { int n ; long long sum = 0; scanf("%d", &n); int x; int ss[100004]; //排序 int cc[100004]; 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 理塘_丁真
发表于 2022-07-05 16:41:29
近乎近乎近乎近乎近乎近乎 #include<iostream> #include<stack> using namespace std; int main(){     int n; &nbs 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

上传者：小小
难度：
9条回答 4063浏览

热门推荐

通过挑战的用户

相关试题

有效序列的数量

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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