http://codeforces.com/contest/447/problem/C
题意:给你n个数的序列,然后让你改变其中的一个数,求得最长上升连续序列的长度值。
思路:先从左边开始求出连续递增序列的值记录在l数组,然后从右边开始再求一遍连续递增序列的值记录在r数组中,然后从2-n-1位置遍历,改变其中的一个数,使得组成一个新的递增序列,求出长度最大值就可以。
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 1000100
#define ll long long
using namespace std;
const int inf=<<; int n,m,k;
ll a[maxn];
char str[maxn];
int l[maxn],r[maxn]; int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
{
cin>>a[i];
}
l[]=;
for(int i=; i<=n; i++)
{
if(a[i]>a[i-])
{
l[i]=l[i-]+;
}
else
l[i]=;
}
r[n]=;
for(int i=n-; i>=; i--)
{
if(a[i+]>a[i]) r[i]=r[i+]+;
else r[i]=;
}
int ans=max(r[]+,l[n-]+);
for(int i=; i<n; i++)
{
if(a[i+]-a[i-]>) ans=max(ans,l[i-]+r[i+]+);
else ans=max(ans,max(r[i+],l[i-])+);
}
printf("%d\n",ans);
return ;
}