首页 > 其他 > 详细

DZY Loves Sequences

时间:2015-07-16 18:47:18      阅读:213      评论:0      收藏:0      [点我收藏+]
Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Description

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.

Input

The first line contains integer n (1 ≤ n ≤ 105). The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

In a single line print the answer to the problem — the maximum length of the required subsegment.

Sample Input

Input
6
7 2 3 1 5 6
Output
5

Hint

You can choose subsegment a2, a3, a4, a5, a6 and change its 3rd element (that is a4) to 4.

代码有毒! 调了好久好久。

技术分享
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int main()
 6 {
 7     int i,j;
 8     int b[100005],c[100005];
 9     int n,a[100005],ma;
10     while(scanf("%d",&n)!=EOF)
11     {
12         memset(b,0,sizeof(b));
13         memset(a,0,sizeof(a));
14         memset(c,0,sizeof(c));
15         for(i=1;i<=n;i++)
16             scanf("%d",&a[i]);
17         ma=0;
18         a[0]=0,a[n+1]=0,b[0]=0,b[n+1]=0,c[0]=0,c[n+1]=0;
19         for(i=1;i<=n;i++)
20         {
21             if(a[i]>a[i-1])
22                 b[i]=b[i-1]+1;
23             else
24                 b[i]=1;
25             if(b[i]>ma)
26                 ma=b[i];
27         }
28         for(i=n;i>=1;i--)
29         {
30             if(a[i]<a[i+1])
31                 c[i]=c[i+1]+1;
32             else
33                 c[i]=1;
34             if(c[i]>ma)
35                 ma=c[i];
36         }
37         for(i=1;i<=n;i++)
38         {
39             if(a[i+1]-a[i-1]>=2)
40             {
41                 ma=max(ma,b[i-1]+c[i+1]+1);
42             }
43             else
44             {
45                 ma=max(ma,max(b[i-1]+1,c[i+1]+1));
46             }
47         }
48         printf("%d\n",ma);
49     }
50     return 0;
51 }
View Code

 

DZY Loves Sequences

原文:http://www.cnblogs.com/cyd308/p/4651657.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!