假設有序列：2,1,3,5，求一個最長上升子序列就是2,3,5或者1,3,5，長度都為3。
LIS算法的思想是：
設存在序列a。
① 如果只有一個元素，那么最長上升子序列的長度為1；
② 如果有兩個元素，那么如果a[1]>a[0]，則最長上升子序列的長度為2，a[1]為該最長上升子序列的最后一個元素;若a[1]<a[0]，則最長上升子序列的長度為1，a[0]和a[1]均為 其最長上升子序列的最后一個元素。
③ 如果由三個元素，那么如果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]結尾的最長上升子序列的長度。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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 152
樣例輸出：
0
4
在用LIS來解這道題的時候，可以這樣考慮：
首先從前向后用LIS求一遍以每一個元素結尾的最長上升子序列的長度，然后將數組逆序，再用LIS求一遍以每一個元素結尾的最長上升子序列的長度。
得到兩個數組b1,b2。
b1,b2對應相加再減去重復的一個，就是最長的'山峰'。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
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> |
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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; }} |
以上就是小編為大家帶來的使用java實現LIS算法,出操隊形的問題的全部內容了，希望對大家有所幫助，多多支持服務器之家~
