题解 | 合唱队

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    heights := make([]int, n+1)
    for i := 1; i <= n ; i ++ {
        fmt.Scan(&heights[i])
    }
    dp1 := make([]int, n+1)
    for i := 1; i <= n; i ++ {
        dp1[i] = 1
        for j := 1; j < i ; j ++ {
            if heights[i] > heights[j] {
                if dp1[j]+1 > dp1[i] {
                    dp1[i] = dp1[j]+1
                }
            } 
        }
    }

    dp2 := make([]int, n+1)
    for i := n; i > 0; i -- {
        dp2[i] = 1
        for j := n; j > i ; j -- {
            if heights[i] > heights[j] {
                if dp2[j] + 1 > dp2[i] {
                    dp2[i] = dp2[j] + 1
                }
            }
        }
    }

    maxKeep := 0

    for i := 1; i <= n; i ++ {
        total := dp1[i]+dp2[i] - 1
        if total > maxKeep {
            maxKeep = total
        }
    }

    fmt.Println(n-maxKeep)
}