题解 | #合唱队#

package main

import (
    "fmt"
)

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

func removeLessElement(nums []int) int {
    size := len(nums)

    // left[i]: 表示在下标 i 左侧最长上升子序列的长度，包括 i
    // left[j]: 表示在下标 j 右侧最长下降子序列的长度，包括 j
    left := make([]int, size)
    right := make([]int, size)

    // 初始化
    for i:=0; i<size; i++ {
        left[i] = 1
        right[i] = 1
    }

    // 收集左侧元素
    for j:=1; j<size; j++ {
        for i:=0; i<j; i++ {
            if nums[i] < nums[j] {
                left[j] = max(left[j], left[i] + 1)
            }
        }
    }

    // 收集右侧元素
    for i:=size-2; i>=0; i-- {
        for j:=size-1; j>i; j-- {
            if nums[i] > nums[j] {
                right[i] = max(right[i], right[j] + 1)
            }
        }
    }

    // 枚举每个元素为中间元素
    var maxLength int
    for i:=0; i<size; i++ {
        maxLength = max(maxLength, left[i] + right[i] - 1)
    }

    return maxLength
}

func main() {
    var N int
    var nums []int

    fmt.Scan(&N)

    for i:=0; i<N; i++ {
        var num int
        fmt.Scan(&num)
        nums = append(nums, num)
    }

    fmt.Println(N - removeLessElement(nums))
}

// 本题输入为一行数字，所以采用 fmt.Scan(&n)

// 本题有点像 【接雨水】，先计算出左右两侧最高的柱子，然后累加每个柱子上可以存的水量
// ref: *************************************************