1.信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) 1283登山
根据题意，该题的图形为单峰的序列，从左至右先递增再递减，我们可以依次枚举峰值
然后再分别计算左右两个子序列的长度
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1010; 5 6 int n; 7 int a[N],f[N],g[N]; 8 int _; 9 10 int main () 11 { 12 13 scanf("%d", &n); 14 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 15 16 int res = 0; 17 for (int i = 1; i <= n; i ++ )//从前往后计算每一个状态 18 { 19 f[i] = 1;//表示以i结尾的子序列的长度为1 只有a[i]这一个数 20 for (int j = 1; j < i; j ++ ) 21 if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); 22 } 23 24 //左右两个子序列互相独立 25 for (int i = n; i ; i -- )//倒着的另一个子序列 26 { 27 g[i] = 1;//表示以i结尾的子序列的长度为1 只有a[i]这一个数 28 for (int j = n; j > i; j -- ) 29 if(a[i] > a[j]) g[i] = max(g[i],g[j] + 1); 30 } 31 32 for (int i = 1; i <= n; i ++ ) res = max(res,f[i] + g[i] - 1); //枚举所有点； 33 34 cout << res << endl; 35 return 0; 36 }