$$\color{Red}{登山-先上升后下降的子序列}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

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

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

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

输入格式
第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式
输出一个整数，表示最多能浏览的景点数。

数据范围

2 ≤ N ≤ 1000

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

证明

这道题看上去很类似怪盗基德，但是怪盗基德是选择一条最长的，而且单向路径。

这道题的区别是最高点确定后，两边的路径确定，显然可以求左右两端各自起点的最长上升子序列，然后对每个点的两个规划值求和，再减1：
因为到达山顶只有一次，两个规划都算上了这一步。

java

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

public class Main {
    static int N = 1010, n;
    static int[] f = new int[N];
    static int[] g = new int[N];
    static int[] a = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int res = 0;
        n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        //正向上升子序列
        Arrays.fill(f, 1);
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(str[i - 1]);
            for (int j = 1; j < i; j++) {
                if (a[i] > a[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        //反向上升子序列
        Arrays.fill(g, 1);
        for (int i = n; i >= 1; i--) {
            for (int j = n; j > i; j--) {
                if (a[i] > a[j])
                    g[i] = Math.max(g[i], g[j] + 1);
            }
            res = Math.max(res, f[i] + g[i] - 1);
        }
        System.out.println(res);
    }
}

python

N = 1010
f = [1] * N
g = [1] * N
a = [0] * N

n = int(input())
a = [0] + [int(x) for x in input().split()]
# 左起点最长上升子序列
for i in range(1, n+1):
    for j in range(1, i):
        if a[i] > a[j]:
            f[i] = max(f[i], f[j] + 1)

# 右起点最长上升子序列
for i in range(n, 0, -1):
    for j in range(n, i, -1):
        if a[i] > a[j]:
            g[i] = max(g[i], g[j] + 1)

res = 0
for i in range(1, n+1): res = max(res, f[i] + g[i] - 1)
print(res)