UVa 1471 防线

 1 #include<iostream>  
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 100000 * 2 + 5;
 6 
 7 int n;
 8 int a[maxn];
 9 int f[maxn], g[maxn],d[maxn];
10 
11 int main()
12 {
13     //freopen("D:\\txt.txt", "r", stdin);
14     int t;
15     cin >> t;
16     while (t--)
17     {
18         cin >> n;
19         for (int i = 1; i <= n; i++)
20             cin >> a[i];
21         f[1] = 1;
22         for (int i = 2; i <= n; i++)
23             f[i] = a[i] > a[i - 1] ? f[i - 1] + 1 : 1;
24         g[n] = 1;
25         for (int i = n - 1; i >= 1; i--)
26             g[i] = a[i] < a[i + 1] ? g[i + 1] + 1 : 1;
27         int ans = 0;
28         for (int i = 1; i <= n; i++)
29             d[i] = 1 << 30;
30         for (int i = 1; i <= n; i++)
31         {
32             //low_bound的返回值就是以a[i]为尾的连续递增子序列
33             int len = (lower_bound(d + 1 , d + 1 + i , a[i]) - (d + 1)) + g[i];
34             ans = max(len, ans);
35             d[f[i]] = min(a[i], d[f[i]]); //如果以i结尾的最大连续递增子序列个数相同，那么选择数小的
36         }
37         cout << ans << endl;
38     }
39     return 0;
40 }