③ 如果由三個元素，那麼如果a[2]>a[0],a[2]>a[1],則a[2]可以作為a[0]或a[1]所在最長上升子序列的最後一個元素。那選擇哪一個序列就要看a[0],a[1]哪一個所在的序列比較長。
④ 擴展到n個元素，就是看以a[n]為最後一個元素的最長上升子序列的長度是多少。
定義兩個數組，一個是a,一個是b。
a存放原始數據，b[i]存放的是以a[i]結尾的最長上升子序列的長度。
代碼如下：
class Lmax{
public static void Lmax(int[] a,int[] b){
b[0]=1;
for(int i=1;i<a.length;i++){
int countmax=0;
for(int j=0;j<i;j++){
if(a[i]>a[j]&&b[j]>countmax){
countmax=b[j]; //记录下元素数值比a[i]小的但是对应子序列最长的子序列长度
}
}
b[i]=countmax+1; //a[i]对应的最长子序列长度是
}
}
}登入後複製
二、出操隊形
題目描述：
在讀高中的時候，每天早上學校都要組織全校的師生進行跑步來鍛鍊身體，每當出操令吹響時，大家就開始往樓下跑了，然後身高矮的排在隊伍的前面，身高較高的就要排在隊尾。突然，有一天出操負責人想了一個主意，想要變換一下隊形，就是當大家都從樓上跑下來後，所有的學生都隨機地佔在一排，然後出操負責人從隊伍中抽取出一部分學生，使得隊伍中剩餘的學生的身高從前往後看，是一個先升高後下降的「山峰」形狀。據說這樣的形狀能夠為大家帶來好運，祝福大家在學習的道路 上勇攀高峰。 (註，山峰只有一邊也符合條件，如1,1、2,2、1均符合條件)
輸入：
輸入可能包含多個測試樣例。
對於每個測試案例，輸入的第一行是一個整數n(1<=n<=1000000)：代表將要輸入的學生個數。
輸入的第二行包括n個整數：代表學生的身高（cm）(身高為不高於200的正整數)。
輸出：
對應每個測試案例，輸出需要抽出的最少學生人數。
樣本例輸入：
6
100 154 167 159 132 105
5
152 152 152 152 150%
在用LIS來解這題的時候，可以這樣考慮：首先從前向後用LIS求一遍以每一個元素結尾的最長上升子序列的長度，然後將數組逆序，再用LIS求一遍以每一個元素結尾的最長上升子序列的長度。 得到兩個數組b1,b2。 b1,b2對應相加再減去重複的一個，就是最長的'山峰'。 public class peak {
public static void main (String[] args)
{
int n;
int re;
do{
Scanner in = new Scanner(System.in);
n = in.nextInt();
}while(n<0||n>100000);
int []a = new int[n]; //原始数组
int []ar = new int[n]; //逆序数组
Scanner in = new Scanner(System.in);
for(int i=0;i<n;i++){
a[i]=in.nextInt();
}
int[] b1 = new int[n];
@SuppressWarnings("unused")
int[] b2 = new int[n];
Lmax.Lmax(a, b1);
ar=reverse.reverse(a);
Lmax.Lmax(ar, b2); //求解逆序数组的最长上升子序列
b2=reverse.reverse(b2); //将逆序数组的最长上升子序列逆序以便和原始数组的最长上升子序列对应相加
re = result.result(b1, b2);
System.out.print(re);
}
}<br><br><br><br>登入後複製
class result{
public static int result(int[] a,int[] b){
int max=0;
int[] c = new int[a.length];
for(int i=0;i<a.length;i++){
c[i]=a[i]+b[i];
}
Arrays.sort(c);
max=c[c.length-1]-1; //对应相加最长的再减去重复的一个人
return a.length-max;
}
}登入後複製
