题解 | #购物单#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class dl{
int num;
int height;
int left;
int right;
int max;
public dl(int a,int b){
this.num = a;
this.height = b;
}
}
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s0 = br.readLine();
int number = Integer.parseInt(s0);
int[] h = new int[number+1];
String[] s1 = br.readLine().split(" ");
for(int i=1;i<=number;i++){
h[i] = Integer.parseInt(s1[i-1]);
}
dl[] team = new dl[number+1];
for(int i=1;i<=number;i++){
team[i] = new dl(i,h[i]);
}
for(int i=2;i<=number;i++){
int left_max=0;
for(int j=i-1;j>=1;j--){
if(team[j].height<team[i].height&&team[j].left>=left_max){
team[i].left = team[j].left+1;
left_max = team[j].left;
}
}
}
for(int i=number-1;i>=1;i--){
int right_max=0;
for(int j=i+1;j<=number;j++){
if(team[j].height<team[i].height&&team[j].right>=right_max){
team[i].right = team[j].right+1;
right_max = team[j].right;
}
}
}
for(int i=1;i<=number;i++){
team[i].max = team[i].left+team[i].right;
}
int max=0;
for(int i=1;i<=number;i++){
if(team[i].max>max){
max = team[i].max;
}
}
System.out.println(number-1-max);
}
}