$$\color{Red}{怪盗基德的滑翔翼-双向上升子序列}$$

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

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

证明

显然这题是一个最长上升子序列问题，但是我们可以选择左或者右边单向前进，我们可以简单的把它分成同时算左起点的最长上升子序列，同时也算右起点开始的最长上升子序列。但是并不是左起点的最长下降子序列，因为左起点开始的下降子序列，算的是从左为起点，终点为f[i]的最长下降序列长度，而题意应当是从山顶开始，到最右端的最长下降子序列长度。

这题最大的关键就是，第一步对f[i] = 1赋值，避免第一次动态规划的赋值f[i]干扰最终的结果。

当然也可以直接对答案加1，把最开始第一个数字的序列长度加上。

1 java

import java.util.*;
import java.io.*;

public class Main{
    static int N = 110;
    static int a[] = new int [N];
    static int f[] = new int [N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());

        while(k -- > 0) {
            int n = Integer.parseInt(br.readLine());
            String str [] = br.readLine().split(" ");
            for(int i=1; i<=n; i++) a[i] = Integer.parseInt(str[i-1]);
            int res = 0;
            //正向dp
            for(int i=1; i<=n; i++) {
                f[i] = 1;
                for(int j=1; j<i; j++)
                    if (a[i] > a[j])
                        f[i] = Math.max(f[i], f[j] + 1);
                res = Math.max(res, f[i]);
            }
            //反向dp
            for(int i=n; i>=1; i--) {
                f[i] = 1;
                for(int j=n; j>i; j--)
                    if (a[i] > a[j])
                        f[i] = Math.max(f[i], f[j] + 1);
                res = Math.max(res, f[i]);
            } 
            System.out.println(res);
        }
    }
}

2 python

N = 110
f = [1] * N
a = [0] * N

k = int(input())
for i in range(k):
    n = int(input())
    a = [0] + [int(x) for x in input().split()]
    # 正向最长上升子序列
    res = 0
    for j in range(1, n+1):
        f[j] = 1
        for k in range(1, j):
            if a[j] > a[k]:
                f[j] = max(f[j], f[k] + 1)
        res = max(res, f[j])
    # 反向最长上升子序列   
    for j in range(n, 0, -1):
        f[j] = 1
        for k in range(n, j, -1):
            if a[j] > a[k]:
                f[j] = max(f[j], f[k] + 1)
        res = max(res, f[j])

    print(res)