题解 | #合唱队#

/*
* dp[i]:表示以元素i为最高身高的最长队列
* f[i]:表示以元素i为尾节点的最长递增序列
* g[i]:表示以元素i为起始节点最长递减序列
* 则dp[i] = f[i] + g[i] - 1;
*/
import java.util.Scanner;

public class 合唱队 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
//输入学生总数
int student = sc.nextInt();
//输入学生身高
int[] height = new int[student];
for (int i = 0; i < student; i++) {
height[i] = sc.nextInt();
}
System.out.println(student - calue(student, height));
}
}

private static int calue(int student, int[] height) {
    int[] dp = new int[student]; int[] f = new int[student] ; int[] g = new int[student];
    //先求f[i]
    lengthOfUpLst(student,height,f);
    //在求g[i]
    lengthOfDownLst(student,height,g);
    //求dp[i]
    for (int i = 0; i < student; i++) {
        dp[i] = f[i] + g[i] - 1;
    }
    int maxLen = dp[0];
    for (int i = 0; i < student; i++) {
        maxLen = maxLen>dp[i] ? maxLen:dp[i]; 
    }
    return maxLen;
}
//最长递减序列
private static void lengthOfDownLst(int len, int[] height, int[] g) {
    if (len==0) {
        return;
    }
    g[len-1] = 1;
    for (int i = len-2; i >=0 ; i--) {
        int max = 1;
        for (int j = len-1; j > i; j--) {
            if (height[j]<height[i]) {
                max = max>(g[j]+1) ? max:(g[j]+1);
            }
        }
        g[i] = max;
    }
}
//最长递增序列
private static void lengthOfUpLst(int len, int[] height, int[] f) {
    if (len==0) {
        return;
    }
    f[0] = 1;
    for (int i = 1; i < len; i++) {
        int max = 1;
        for (int j = 0; j < i; j++) {
            if(height[j]<height[i]){
                max = max>(f[j]+1) ? max:(f[j]+1);
            }
        }
        f[i] = max;
    }
}
//

}