题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1551
升级版：Uva 1471
题意：
让你求删除一段连续的子序列之后的LIS。
题解：
预处理：先求一个last[i]，以a[i]为开始的合法最长上升子序列的长度。再求一个pre[i]，以a[i]为结尾的合法最长上升子序列长度。
答案应该为
max（以j结束的合法最长上升子序列长度） + 以a[i]为开始的合法最长上升子序列长度。 其中j<a[i]。
1）通过树状数组维护区间最值。
2）通过LIS 维护。（详细请看http://www.cnblogs.com/denghaiquan/p/6761600.html）
1 #include <iostream>View Code
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <string>
6 #include <vector>
7 #include <map>
8 #include <set>
9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define ms(a, b) memset((a), (b), sizeof(a))
16 //#define LOCAL
17 #define eps 0.0000001
18 typedef long long LL;
19 const int inf = 0x3f3f3f3f;
20 const int maxn = 10000+10;
21 const int mod = 1000000007;
22 int a[maxn], pre[maxn], last[maxn], c[maxn];
23 int n;
24 int lowbit(int x){
25 return x&(-x);
26 }
27 int ask(int x)
28 {
29 int ans = 0;
30 while(x>0){
31 ans = max(ans, c[x]);
32 x-=lowbit(x);
33 }
34 return ans;
35 }
36 void updata(int x, int d)
37 {
38 while(x <= 1e4){
39 c[x] = max (c[x] , d);
40 x += lowbit(x);
41 }
42 }
43 void solve()
44 {
45 int ans = 0;
46 ms(c, 0);
47 for(int i=1;i<=n;i++) scanf("%d", &a[i]);
48 //last[i] 是第i个开始和合法后缀
49 last[n] = 1;
50 for(int i = n-1; i>0;i--){
51 if(a[i] < a[i+1]){
52 last[i] = last[i+1] + 1;
53 }else last[i] = 1;
54 }
55 //pre[i] 是第i个结束的合法前缀
56 pre[1] = 1;
57 for(int i=2;i<=n;i++){
58 if(a[i] > a[i-1]){
59 pre[i] = pre[i-1] + 1;
60 }else pre[i] = 1;
61 }
62 for(int i=1;i<=n;i++){
63 ans = max(ans, last[i] + ask(a[i]-1));
64 updata(a[i], pre[i]);
65 }
66 printf("%d\n", ans);
67 }
68 int main()
69 {
70 #ifdef LOCAL
71 freopen("jumping.in", "r", stdin);
72 // freopen("output.txt", "w", stdout);
73 #endif // LOCAL
74 while(~scanf("%d", &n)){
75 solve();
76 }
77 return 0;
78 }
升级版，应该数的范围在1e9所以无法用树状数组维护。只能用LIS或者set来维护。