合唱队形

【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, ¡­, K，他们的身高分别为T1, T2, ¡­, TK，则他们的身高满足T1 < T2 < ¡­ < Ti , Ti > Ti+1 > ¡­ > TK (1≤i≤K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入文件】输入文件chorus.in的第一行是一个整数N（2 ≤ N ≤ 100），表示同学的总数。第 二行有n个整数，用空格分隔，第i个整数Ti（130 ≤ Ti ≤ 230）是第i位同学的身高（厘米）。
【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
解法1：动态规划方法 

我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设
a为身高序列，其中a[i]为同学i的身高；
b 为由左而右身高递增的人数序列，其中 b[i]为同学1¨同学i间（包括同学i）身高满足递增顺序的最多人数。显然
 b[i]= {b[j]|同学j的身高<同学i的身高}+1；
c为由右而左身高递增的人数序列，其中c[i]为同学n¨同学i间（包括同学i）身高满足递增顺序的最多人数。显然
 c[i]= {c[j]|同学j的身高<同学i的身高}+1；
由上述状态转移方程可知，计算合唱队形的问题具备了最优子结构性质(要使b[i]和c[i]最大，子问题的解b[j]和c[k]必须最大(1≤j≤i-1 ，i+1≤k≤n))和重迭子问题的性质(为求得b[i]和c[i]，必须一一查阅子问题的解b[1]¨b[i-1]和c[i+1]¨c[n])，因此可采用动态规划的方法求解。
显然，合唱队的人数为 (公式中同学i被重复计算，因此减1)，n减去合唱队人数即为解。 

readln(n); {读学生数}
 for i:=1 to n do read(a[i]); {读每个学生的身高}
 fillchar(b,sizeof(b),0);fillchar(c,sizeof©,0);{身高满足递增顺序的两个队列初始化}
 for i:=1 to n do{按照由左而右的顺序计算b序列}
 begin
b[i]:=1;
for j:=1 to i-1 do if (a[i]>a[j])and(b[j]+1>b[i]) then b[i]:=b[j]+1;
 end;{for}
 for i:=n downto 1 do{按照由右而左的顺序计算c序列}
 begin
 c[i]:=1;
 for j:=i+1 to n do if (a[j]<a[i])and(c[j]+1>c[i])then c[i]:=c[j]+1;
end;{for}
 max:=0;{计算合唱队的人数max（其中1人被重复计算）}
 for i:=1 to n do if b[i]+c[i]>max then max:=b[i]+c[i];
 writeln(n-max+1); {输出出列人数}

 这个算法的时间复杂度为O(n2) 
解法2：二分法
 设x为当前身高满足递增顺序的队列，其中x[i]为第i高的队员身高；a序列、b序列和c序列的定义如解法1。
 设x[i]的初始值为∞(1≤i≤n)，b[0]为0。我们从同学1出发，按照由左而右的顺序计算身高递增的人数序列b。在计算b[i]时，通过二分法找出区间x[1]¨x[i]中身高矮于同学i的元素个数min（x区间的左右指针为min和max，中间指针为mid）
 在计算出b序列后，再采用类似方法由右而左计算身高递增的人数序列c。最后得出出列人数为
 n- (公式中同学i被重复计算，因此减1)。 

readln(n);{读学生数}
 for i:=1 to n do read(a[i]);{读每个学生的身高}
 for i:=1 to n do x[i]:=maxlongint;{身高满足递增顺序的队列初始化}
 b[0]:=0;
 for i:=1 to n do{由左而右计算b序列}
 begin
 min:=0;max:=i;{设x区间的左右指针}
 while min<max-1 do{若x区间存在，则通过二分法计算同学i前身高满足递增顺序的最多人数min}
 begin
 mid:=(min+max) div 2;{计算中间指针}
 if x[mid]<a[i]
 then min:=mid{搜索右区间}
 else max:=mid{搜索左区间}
 end;{while}
 b[i]:=min+1;x[min+1]:=a[i]{同学1¨同学i间（包括同学i）最多有min+1个同学可排成身高递增的队列}
 end;{for}
 

for i:=1 to n do x[i]:=maxlongint; {身高满足递增顺序的队列初始化}
 c[0]:=0;
 for i:=n downto 1 do{由右而左计算c序列}
 begin
 min:=0;max:=i;
 while min<max-1 do
 begin
 mid:=(min+max) div 2; 设x区间的左右指针}
 if x[mid]<a[i]
 then min:=mid{搜索右区间}
 else max:=mid{搜索左区间}
 end;{while}
 c[i]:=min+1;x[min+1]:=a[i] {同学n¨同学i间（包括同学i）最多有min+1个同学可排成身高递增的队列}
 end;{max}
 max:=0;{计算合唱队的人数max（其中1人被重复计算）}
 for i:=1 to n do if b[i]+c[i]>max then max:=b[i]+c[i];
 writeln(n+1-max);{输出出列人数}

第二种解法的算法的时间复杂度为O(n*log n)