题意：
你可以最多改变序列中的一个数字 求 序列最长的连续递增子串长度
思路：
首先可以把原串划分成单调递增的若干段子串 然后通过改变一个数字 看能拼出多长的串
首先对于一段 可以用他的长度更新答案 如果他旁边有别的串 那他至少可以占用别人的一个数字
其次如果是两个段拼接 需要考虑三种情况 即 .+---- 、 ----+. 、-----+----- 说白了就是有一段可能是只有一个数字
这里只要分类讨论即可
最后 有可能是三段的拼接 只有一种情况 ---- + . + ----- 即第二段就一个数字 也是讨论一下即可
代码：
#include#include #include using namespace std; #define N 100010 int a[N],st[N],ed[N]; int ans,n; int main() { int i,id; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) scanf("%d",&a[i]); ans=1; id=1; st[1]=1; for(i=2;i<=n;i++) { if(a[i]<=a[i-1]) { ed[id]=i-1; id++; st[id]=i; } } ed[id]=n; for(i=1;i<=id;i++) { ans=max(ans,ed[i]-st[i]+1); // ------ if(i+1<=id||i-1>=1) ans=max(ans,ed[i]-st[i]+2); // have next if(i+1<=id) { if(st[i]==ed[i]) // . ----- { ans=max(ans,ed[i+1]-st[i]+1); } else if(st[i+1]==ed[i+1]) // ----- . { ans=max(ans,ed[i+1]-st[i]+1); if(i+2<=id) // ----- . ------ { if(a[st[i+2]]-a[ed[i]]>1) { ans=max(ans,ed[i+2]-st[i]+1); } } } else // ----- ----- { if(a[st[i+1]+1]-a[ed[i]]>1 || a[st[i+1]]-a[ed[i]-1]>1) { ans=max(ans,ed[i+1]-st[i]+1); } } } } printf("%d\n",ans); } return 0; }