problem ― the maximum length of the required subsegment. Sample test(s) input
6
7 2 3 1 5 6
output
5
Note
You can choose subsegment a2,?a3,?a4,?a5,?a6 and change its 3rd element (that is a4) to 4.
给你一个序列S，让你可以改变序列中的一个值，使得此序列的一个子序列为上升序列。求此子序列最长是多少。
设r[i]为在位置i上最长的上升序列个数（从序列头开始）,l[i]为在位置i上最长的上升序列的个数（从序列尾开始）。
如果S[i+1]-S[i-1]>1，那么最长可能是max(ans,r[i-1]+l[i+1]+1)
否则最长可能是max(ans,max(r[i-1],l[i+1])+1)
//46 ms 1200 KB
#include
#include
#define M 100007 using namespace std; int s[M],r[M],l[M]; int main() { int n,ans; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); r[1]=1; for(int i=2;i<=n;i++) if(s[i]>s[i-1])r[i]=r[i-1]+1; else r[i]=1; l[n]=1; for(int i=n-1;i>=1;i--) if(s[i]
n)ans=n; printf("%d\n",ans); }