题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
import java.util.*; public class Main { public static void main(String[] args) { Scanner fzhinput = new Scanner(System.in); int num = fzhinput.nextInt(); int sgnum [] = new int[num]; int sgsz,sgsz1,ydnum=0; int maxnum=0,ws=0; for(int i=0;i<num;i++){ sgnum [i]=fzhinput.nextInt(); } int lidl[] = new int[num]; int rddl[] = new int[num]; Arrays.fill(lidl, 1); Arrays.fill(rddl, 1); for(int i=1;i<num;i++){ for(int j=0;j<i;j++){ if(sgnum[i]>sgnum[j]){ lidl[i]=Math.max(lidl[i],lidl[j]+1); } } } for (int i = num - 2; i >= 0; i--) { for (int j = num - 1; j > i; j--) { if(sgnum[i]>sgnum[j]){ rddl[i]=Math.max(rddl[i],rddl[j]+1); } } } int maxdwnum=0; for(int i=0;i<num;i++){ maxdwnum =Math.max(maxdwnum,lidl[i]+rddl[i]-1); } System.out.println(num-maxdwnum); } }