题解 | #牛牛的数列#
题解：
首先求左右两个方向可以组成的最长连续上升子序列
然后求断点的位置，左右两边接上最长上升子序列
最后输出答案
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 1e5 + 10 ;
int w[N] , l[N] , r[N] ;
int main(void)
{
int n ;
cin >> n ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i ++) scanf("%d" , &w[i]) ;
w[0] = -0x3f3f3f3f , w[n + 1] = 0x3f3f3f3f ;
for(int i = 1 ; i <= n ; i ++)
{
l[i] = 1 ;
if(i > 1 && w[i] > w[i - 1]) l[i] = l[i - 1] + 1 ;
ans = max(ans , min(l[i] +1, n+1)) ;
}
for(int i = n ; i ; i -- )
{
r[i] = 1 ;
if(i < n && w[i] < w[i + 1]) r[i] = r[i + 1] + 1 ;
ans = max(ans , min(r[i] +1, n +1)) ;
}
for(int i = 1 ; i <= n ; i ++ )
if(w[i - 1] + 1 < w[i + 1]) ans = max(ans , l[i - 1] + r[i + 1] + 1) ;
cout << ans << endl ;
}
腾讯HR面1998人在聊
查看7道真题和解析
