华为 合唱队 算法

云深处

题目描述


　　计算最少出列多少位同学，使得剩下的同学排成合唱队形
　　说明：
　　N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。


输入描述:
　　整数N



输出描述:
　　最少需要几位同学出列


输入例子:

8
186 186 150 200 160 130 197 200



输出例子:

4





最少几位同学出列，可以转换成查找 数组中，每个数组元素的最长增序列 跟最长减序列





package org.huawei.test;
import org.junit.Test;
import java.util.Arrays;
/**
* Created by Administrator on 2016/10/7 0007.
*/
public class man {//合唱团

@Test
public  void que(){
int [] high = {186,186,150,200,160,130,197,200};//input输入
int [] tagUp = new int[high.length];
int [] tagDown = new int[high.length];
int [] tag = new int[high.length];
for ( int i = 0 ; i < high.length;i++){
for(int j = i ; j < high.length; j++){//求得每个位置的最长增序
if (j == high.length-1){
break;
}
if (high[j] > high[j+1]){
tagUp +=1;
}else{
break;
}
}
for (int j = i; j > 0; j--){//求得每个位置的最长减序
if (j == 0){
break;
}
if (high[j]>high[j-1]){
tagDown +=1;
}else{
break;
}
}
}
for(int i = 0; i < tag.length;i++){
if (tagDown == 0 || tagUp ==0){
tag = 0;
}else{
tag = tagUp + tagDown;
}
}
for(int tmp : tag){
System.out.println(tmp);
}
Arrays.sort(tag);
System.out.println(tag.length-tag[tag.length-1]-1);
}
}
　　预计有些极端情况没有被想到