0
已解决
高级光能
题目链接： 酷町堂：6680
酷町序列经验值：1200
题目描述 Deion
给你一串连续的数字，这些数字刚开始是单调递增或者保持恒定的，接着是一段单调递减或者保持恒定不变的。比如2 3 5 5 4 1 1，我们把这种数称为酷町序列。如果只是单调递增或者单调递减也算是一个酷町序列。
现在给你N个数，请你求出长度最大的酷町序列
【注】两个酷町序列之间会有重叠部分
输入描述 Input Deion
第1行: 一个单独的整数: N
第2到第N+1行: 第i+1行包含一个单独的整数ai
输出描述 Output Deion
1行: 一个单独的整数，表示最长的酷町序列
样例输入 Sample Input
7 3 2 3 5 4 1 6
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
1 ≤ N ≤ 10,000
1 ≤ a~i ~≤ 1,000,000,000
【样例说明】
在最长的酷町序列为2, 3, 5, 4, 1. 其他的酷町序列包括3, 2和1, 6。
【提示】
如果你知道一个酷町序列里最大的那个数，你会发现，找到这个酷町序列的长度是很容易的哦。
0
已采纳
初级光能
@汪艾辰 首先就是循环遍历1到n输入然后进行f数组的运算，然后遍历n到1进行g数组的运算，最后循环遍历1到n用max函数求ans和f[i]+g[i]-1的最大值，最后输出ans
0
0
初级光能
枚举a数组每一个数（当做a[i]是最大的）
0
初级光能
lr向左向右遍历a[r]，a[l]都一定小于a[r+1],a[l-1],r++,l--
0
初级光能
核心，r同理
0
初级光能
前面那个同学给的是思路时间复杂度是O(n^2)，我给的时间复杂度是O(n)
f[i] 以第i个元素结尾的连续不下降序列
如果a[i]大于等于a[i-1]
f[i]更新为f[i-1]+1
否则
f[i]等于1
g[i] 以第i个元素开头的连续不上升序列
如果a[i]大于等于a[i+1]
g[i]更新为g[i+1]+1
否则
g[i]等于1;
