题目描述

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

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

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

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

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

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

样例

输入：
8
186 186 150 200 160 130 197 220
输出：
4

算法

(动态规划LIS) $O(n^2)$

• LIS 模型，思路很经典，上山是找最长上升子序列，下山是找最长下降子序列。
• 这里讲一下需要注意的点：求最长下降子序列的时候是从右往左求，而不能是从左往右求！
• 刚开始写的时候最长上升序列就相当于默写模板，然后下降子序列就理所当然改个符号了，然后提交就WA。仔细一想，问题出在哪里，因为这不是对称的，从左往右求的最长下降子序列 != 从右往左求的最长上升子序列.

其他

• LIS模板题可以看AcWing 895. 最长上升子序列

Go 代码

package main
import "fmt"

const N int = 1010

var (
    n int
    f, g, a [N]int
)

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main(){
    fmt.Scanf("%d", &n)

    for i := 0; i < n; i ++ {
        fmt.Scanf("%d", &a[i])
    }

    for i := 0; i < n; i ++ {
        f[i] = 1

        for j := 0; j < i; j ++ {
            if a[i] > a[j] {
               f[i] = max(f[i], f[j] + 1)
            }    
        }
    }

    for i := n - 1; i >= 0; i -- {
        g[i] = 1

        for j := n - 1; j > i; j -- {
            if a[i] > a[j] {
               g[i] = max(g[i], g[j] + 1)
            }    
        }
    }

    res := 0
    for i := 0; i < n; i ++ {
        res = max(res, f[i] + g[i] - 1)
    }

    fmt.Println(res)
}