本文主要是介绍C. DZY Loves Sequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DZY has a sequence a, consisting of n integers.
We'll call a sequence ai, ai + 1, ..., aj (1 ≤ i ≤ j ≤ n) a subsegment of the sequence a. The value (j - i + 1) denotes the length of the subsegment.
Your task is to find the longest subsegment of a, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.
You only need to output the length of the subsegment you find.
The first line contains integer n (1 ≤ n ≤ 105). The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).
In a single line print the answer to the problem — the maximum length of the required subsegment.
6 7 2 3 1 5 6
5
You can choose subsegment a2, a3, a4, a5, a6 and change its 3rd element (that is a4) to 4.
//题意：给你一个数列，你可以改变这个数列其中任意一个数的值（只能改变一个），找出一个最大子段，其中这个子段要严格递增（只要递增就行且不能出现前后相等）
//AC代码
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<cmath>
const int MAX=100001;
long long xx[MAX];
long long yy[MAX];
using namespace std;
int main()
{
long long n,i,j,m,t,k,As,Ae,Bs,Be,B1,B2,Max,num,a,b,p;
//while(1)
//{
cin>>n;
memset(xx,0,sizeof(xx));
memset(yy,0,sizeof(yy));
As=0;
Ae=0;
Bs=0;
Be=0;
B1=0;
B2=0;
Max=0;
a=1;
b=1;
k=0;
p=0;
cin>>t;
As=t;
xx[a]=t;
a+=1;
for(i=2;i<=n;i++)
{
cin>>m;
//cout<<"OK1"<<i<<endl;
if(t<m)
{
t=m;
xx[a]=m;
a+=1;
}
else
{
Ae=xx[a-1];
As=xx[a-2];
t=m;
yy[b]=m;
b+=1;
break;
}
}
//cout<<"OK"<<endl;
//cout<<As<<" "<<Ae<<" "<<a<<endl;
for(j=i+1;j<=n;j++)
{
cin>>m;
//cout<<m<<" zheshi"<<endl;
//cout<<"OK2 "<<j<<endl;
if(t<m)
{
t=m;
yy[b]=m;
b+=1;
}
else
{
if(j==n)
p=1;
Bs=yy[b-2];
Be=yy[b-1];
B1=yy[1];
B2=yy[2];
//cout<<Bs<<" "<<Be<<" "<<B1<<" "<<B2<<" "<<b<<" acm"<<endl;
if((a-1)==1)
{
if((b-1)==1)
{
num=2;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
else
{
num=b;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
As=Bs;
Ae=Be;
a=b;
b=1;
yy[1]=m;
yy[2]=0;
t=m;
b+=1;
//cout<<As<<" "<<Ae<<" "<<a<<endl;
}
else
{
//cout<<"000"<<endl;
if((b-1)==1)
{
num=a;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
else
{
//cout<<"111"<<endl;
if((B2-Ae>=2)||(B1-As>=2))
{
//cout<<"222"<<endl;
num=a+b-2;
if(Max<=num)
Max=num;
//cout<<As<<" "<<Ae<<" "<<a<<endl;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
else
{
if(a>b)
{
num=a;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
else
{
num=b;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
}
}
As=Bs;
Ae=Be;
a=b;
b=1;
yy[1]=m;
yy[2]=0;
t=m;
b+=1;
}
}
}
//--------------------------------------
if(p==0&&b==1)
{
num=a-1;
if(Max<=num)
Max=num;
}
if(p==0&&b!=1)
{
Bs=yy[b-2];
Be=yy[b-1];
B1=yy[1];
B2=yy[2];
//cout<<As<<" "<<Ae<<" "<<a<<" "<<B1<<" "<<B2<<" "<<b<<" yuweiwei"<<endl;
if((a-1)==1)
{
if((b-1)==1)
{
num=2;
if(Max<=num)
Max=num;
//cout<<"Max="<<Max<<endl;
}
else
{
num=b;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
//cout<<As<<" "<<Ae<<" "<<a<<endl;
}
else
{
//cout<<"000"<<endl;
if((b-1)==1)
{
num=a;
if(Max<=num)
Max=num;
//cout<<"Max="<<Max<<endl;
}
else
{
//cout<<"111"<<endl;
if((B2-Ae>=2)||(B1-As>=2))
{
// cout<<"222"<<endl;
num=a+b-2;
if(Max<=num)
Max=num;
//cout<<"num="<<num<<"Max="<<Max<<endl;
}
else
{
if(a>b)
{
num=a;
if(Max<=num)
Max=num;
//cout<<"Max="<<Max<<endl;
}
else
{
num=b;
if(Max<=num)
Max=num;
// cout<<"Max="<<Max<<endl;
}
}
}
}
}
//cout<<"OKOK"<<endl;
cout<<Max<<endl;
//}
return 0;
}
/*
6
7 7 7 7 7 7
6
7 8 7 7 7 8
6
7 7 8 7 7 8
6
7 3 4 1 6 7
*/
这篇关于C. DZY Loves Sequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
