使用java實現(xiàn)LIS算法,出操隊形的問題

更新時間：2016年09月20日 07:20:45 投稿：jingxian

下面小編就為大家?guī)硪黄褂胘ava實現(xiàn)LIS算法,出操隊形的問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

假設有序列：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]為最后一個元素的最長上升子序列的長度是多少。

定義兩個數(shù)組，一個是a,一個是b。

a存放原始數(shù)據(jù)，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];   //記錄下元素數(shù)值比a[i]小的但是對應子序列最長的子序列長度
        }
      }
       
      b[i]=countmax+1;     //a[i]對應的最長子序列長度是
    }
         
  }
   
}

二、出操隊形

題目描述：

在讀高中的時候，每天早上學校都要組織全校的師生進行跑步來鍛煉身體，每當出操令吹響時，大家就開始往樓下跑了，然后身高矮的排在隊伍的前面，身高較高的就要排在隊尾。突然，有一天出操負責人想了一個主意，想要變換一下隊形，就是當大家都從樓上跑下來后，所有的學生都隨機地占在一排，然后出操負責人從隊伍中抽取出一部分學生，使得隊伍中剩余的學生的身高從前往后看，是一個先升高后下降的“山峰”形狀。據(jù)說這樣的形狀能夠給大家?guī)砗眠\，祝愿大家在學習的道路上勇攀高峰。(注，山峰只有一邊也符合條件，如1,1、2,2、1均符合條件)

輸入：

輸入可能包含多個測試樣例。
對于每個測試案例，輸入的第一行是一個整數(shù)n(1<=n<=1000000)：代表將要輸入的學生個數(shù)。
輸入的第二行包括n個整數(shù)：代表學生的身高（cm）(身高為不高于200的正整數(shù))。

輸出：

對應每個測試案例，輸出需要抽出的最少學生人數(shù)。

樣例輸入：

6

100 154 167 159 132 105

5

152 152 152 152 152

樣例輸出：

0

4

在用LIS來解這道題的時候，可以這樣考慮：

首先從前向后用LIS求一遍以每一個元素結尾的最長上升子序列的長度，然后將數(shù)組逆序，再用LIS求一遍以每一個元素結尾的最長上升子序列的長度。

得到兩個數(shù)組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];           //原始數(shù)組
    int []ar = new int[n];          //逆序數(shù)組
    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);       //求解逆序數(shù)組的最長上升子序列
 
    b2=reverse.reverse(b2);     //將逆序數(shù)組的最長上升子序列逆序以便和原始數(shù)組的最長上升子序列對應相加
     
    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;
  }
}

以上就是小編為大家?guī)淼氖褂胘ava實現(xiàn)LIS算法,出操隊形的問題的全部內(nèi)容了，希望對大家有所幫助，多多支持腳本之家~

您可能感興趣的文章: