算法分析

目标：求最多能浏览多少景点

• 条件1：按照编号递增的顺序来浏览

• 条件2、相邻两个景点不能相同

• 条件3、一旦开始下降，就不能上升了

总结：所有以高度a[i]为转折点，左边到a[i]严格单调上升，a[i]到右边严格单调下降，求所有情况中最长的步数

• 步骤1、预处理出以每个点结尾的正向的最长上升子序列的值f[i]，以每个点结尾的反向的最长上升子序列的值g[i]

• 步骤2、res = max(f[i] + g[i] - 1),i = 1,2,3...n

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N];
    static int[] g = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++) a[i] = Integer.parseInt(s1[i - 1]);

        //预处理
        for(int i = 1;i <= n;i++)
        {
            f[i] = 1;
            for(int j = 1;j < i;j++)
            {
                if(a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        for(int i = n;i >= 1;i--)
        {
            g[i] = 1;
            for(int j = n;j > i;j --)
            {
                if(a[j] < a[i])
                    g[i] = Math.max(g[i], g[j] + 1);
            }
        }
        //计算最大值
        int res = 0;
        for(int i = 1;i <= n;i ++) res = Math.max(res, f[i] + g[i] - 1);
        System.out.println(res);

    }
}

c ++代码($O(nlogn)$版)

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int q[N], f[N], g[N], a[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    int len = 0;
    for(int i = 1;i <= n;i ++)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = a[i];
        len = max(len, l + 1);
        f[i] = len;
    }
    len = 0;
    for(int i = n;i >= 0;i --)
    {
        int l = 0, r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = a[i];
        len = max(len, l + 1);
        g[i] = len;
    }
    int res = 0;
    for(int i = 1;i <= n;i ++) res = max(res, f[i] + g[i] - 1);
    cout << res << endl;
    return 0;
}