这篇文章上次修改于 694 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 704 个字，阅读时长 ≈ 2 分钟

AcWing 1014. 登山

题面：

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

这个题有个小坑，刚读题的时候很容易想出找最长上升子序列，但是再读一遍题，发现开始下山之后也是能逛很多景点的，那这样的话就是要找以下标 $i$ 为终点的最长上升子序列的长度加上以下标$i$为起点的最长下降子序列的长度的和最大的$i$。

#include<iostream>
using namespace std;
int n,ans;
int a[1003],f1[1003],f2[1003];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    //最长上升子序列
    for(int i=1;i<=n;++i){
        f1[i]=1;
        for(int j=1;j<i;++j){
            if(a[j]<a[i]) f1[i]=max(f1[i],f1[j]+1);
        }
    }
    //最长下降子序列
    for(int i=n;i>0;--i){
        f2[i]=1;
        for(int j=n;j>i;--j){
            if(a[j]<a[i]) f2[i]=max(f2[i],f2[j]+1);
        }
    }
    //找和，-1是把多出来的i减掉
    for(int i=1;i<=n;++i) ans=max(ans,f1[i]+f2[i]-1);
    cout<<ans<<endl;
    return 0;
}