题解:
状态表示:
f[i], g[i] 表示正着反着以i为终点的最长上升子序列的最大长度
登山的模型是形如”^”的形状, 具体看代码。
code:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1010, INF = 0x3f3f3f3f;
int n;
int h[N];
int f[N], g[N];
int res = -INF;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> h[i];
for(int i = 1; i <= n; i ++ ) f[i] = g[i] = 1;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j < i; j ++ )
if(h[i] > h[j]) f[i] = max(f[i], f[j] + 1);
for(int i = n; i >= 1; i -- )
for(int j = n; j > i; j -- )
if(h[i] > h[j])
g[i] = max(g[i], g[j] + 1);
for(int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
cout << res << endl;
return 0;
}