思路:最长上升子序列(LIS)的优化以及应用

大家先学习LIS以及其优化方法:https://leetcode.cn/circle/discuss/r3ucvm/

在知道这个知识点以后，我们不难想出，任意一个山峰序列都是由：山峰+ 山峰往左的LIS + 山峰往右的LIS 组成的。

题目描述

小红定义一个长度为$n$的数组为“山峰数组”:存在这样的一个位置，使得这个位置左右两边的全部元素均依次严格递减;使用数学的语言来描述，即存在$x∈(1,n)$使得$a_{i-1}<a_i(i ∈[x,n])$且$a_i>a_{i+1}(i∈[1,x])$。例如 $[1,2,5,4,2]$和$[1,3,2]$是“山峰数组”而$[1],[1,2,3],[1,2,1,2]$和$[1,2,1,1]$不是“山峰数组”。

小红有一个长度为$n$的数组$a_1,a_2,…,a_n$，他想知道在全部的子数组✟中，是“山峰数组”的子数组的长度最大值是多少。

✟:如果数组$a$可以通过从数组$b$的开头删除若干(可能为零或全部)元素以及从结尾删除若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子数组。

输入描述

第一行输入一个整数$n(1≤n≤10^5)$代表数组长度。

第二行输入$n$个整数$a_1,a_2,… ,a_n(1≤a≤10^9)$代表数组的值。

输出描述

在一行上输出一个正整数，代表长度的最大值。

样例1

输入

6
1 1 4 5 1 4

输出

4

提示

最长的“山峰函数“是$[1,4,5,1]$。

样例2

输入

4
1 2 2 1

输出

3