DP Codeforces Round #FF (Div. 1) A. DZY Loves Sequences

 1 /*
 2      DP：先用l，r数组记录前缀后缀上升长度，最大值会在三种情况中产生：
 3         1. a[i-1] + 1 < a[i+1]，可以改a[i]，那么值为l[i-1] + r[i+1] + 1
 4         2. l[i-1] + 1   3. r[i+1] + 1   //修改a[i]
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 #include <cstring>
 9 using namespace std;
10 
11 const int MAXN = 1e5 + 10;
12 const int INF = 0x3f3f3f3f;
13 int a[MAXN];
14 int l[MAXN], r[MAXN];
15 int n;
16 
17 int main(void)      //Codeforces Round #FF (Div. 1) A. DZY Loves Sequences
18 {
19     scanf ("%d", &n);    int ans = 0;
20     for (int i=1; i<=n; ++i)
21     {
22         scanf ("%d", &a[i]);
23         l[i] = 1;
24         if (i > 1 && a[i] > a[i-1])    l[i] = l[i-1] + 1;
25     }
26 
27     for (int i=n; i>=1; --i)
28     {
29         r[i] = 1;
30         if (i < n && a[i] < a[i+1])    r[i] = r[i+1] + 1;
31     }
32 
33     for (int i=1; i<=n; ++i)
34     {
35         ans = max (ans, l[i]);    ans = max (ans, r[i]);
36         if (i > 1 && i < n && a[i-1] + 1 < a[i+1])    ans = max (ans, l[i-1] + r[i+1] + 1);
37         if (i > 1)    ans = max (ans, l[i-1] + 1);
38         if (i < n)    ans = max (ans, r[i+1] + 1);
39     }
40 
41     printf ("%d
", ans);
42 
43     return 0;
44 }
编译人生，运行世界！