题解 | #合唱队#

package main

import (
    "fmt"
)

func main() {
    
    //接收参数
    var count int
    fmt.Scan(&count)
    ori := count 

    nums := make([]int, ori, ori)
    index := 0
    for count > 0 {
       height := 0
       fmt.Scan(&height)

       nums[index] = height
       count--
       index++
    }

    if len(nums) < 3 {
        fmt.Print(0)
        return
    }


    dpUp := make([]int, ori, ori) //dpUp[i] --> 以i为顶点时的递增最高值（顶点，左边元素均小于自己)
    dpDown := make([]int, ori, ori) //dpDown[i] --> 以i为顶点时的递减最高值（顶点，右边元素均小于自己)

    for i := 0; i < ori; i++ {
        dpUp[i] = 1
        dpDown[i] = 1
    }

    for i := 1; i < ori; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dpUp[i] = getMax(dpUp[i], dpUp[j]+1)
            }
        }
    }

     for i := ori-2; i >= 0; i-- {
        for j := ori-1; j > i; j-- {
            if nums[i] > nums[j] {
                dpDown[i] = getMax(dpDown[i], dpDown[j]+1)
            }
        }
    }

    var max int
    for i := 0; i < len(dpDown); i++ {
        max = getMax(max, dpDown[i]+dpUp[i]-1)
    }

    fmt.Println(ori-max)
}

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