题解 | #合唱队#

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	heights := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&heights[i])
	}

	// 计算从左到右的最长递增子序列
	left := make([]int, n)
	for i := 0; i < n; i++ {
		left[i] = 1
		for j := 0; j < i; j++ {
			if heights[j] < heights[i] && left[j]+1 > left[i] {
				left[i] = left[j] + 1
			}
		}
	}

	// 计算从右到左的最长递增子序列
	right := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		right[i] = 1
		for j := n - 1; j > i; j-- {
			if heights[j] < heights[i] && right[j]+1 > right[i] {
				right[i] = right[j] + 1
			}
		}
	}

	// 找到最长的合唱队形长度
	maxLen := 0
	for i := 0; i < n; i++ {
		if left[i]+right[i]-1 > maxLen {
			maxLen = left[i] + right[i] - 1
		}
	}

	// 计算需要出列的同学数
	minOut := n - maxLen

	fmt.Println(minOut)
}

以下是一个使用Golang实现的解决方案：

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	heights := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&heights[i])
	}

	// 计算最长递子序列（LIS）
	lis := longestIncreasingSubsequence(heights)

	// 计算最长减子序列（LDS）
	lds := longestDecreasingSubsequence(heights)

	// 找到最长合唱队形的长度
	maxLen := 0
	for i := 0; i < n; i++ {
		len := lis[i] + lds[i] - 1
		if len > maxLen {
			maxLen = len
		}
	}

	// 计算需要出列的同学目
	minOut := n - maxLen

	fmt.Println(minOut)
}

// 计算最长递增子序列
func longestIncreasingSubsequence(numsint) []int {
	n := len(nums)
	lis := make([], n)

	for i := 0; i < n; i++ {
		lis[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] && lis[j]+1 > lis[i] {
				lis[i] = lis[j] + 1
			}
			}

	return lis
}

// 计算最长递减子列
func longestDecreasingSubsequence(nums []int) []int {
	n := len(nums)
	lds := makeint, n)

	for i := n - 1; i >= 0; i-- {
		lds[i] = 1
		for j := n - 1; j > i; j-- {
			if nums[i] > nums[j] && lds[j]+1 > lds[i] {
				lds[i] = lds[j] + 1
			}
		}
	}

	return lds
}

这个解方案使用动态规划的思想，分别计算最长递增子列（LIS）和最长递减子列（LDS）。然后通过遍历每个同学找到最长合唱队形的长度。最后，需要出列的同学数等于总人减去最长合队形的长度。