假設(shè)有序列：2,1,3,5，求一個(gè)最長(zhǎng)上升子序列就是2,3,5或者1,3,5，長(zhǎng)度都為3。

LIS算法的思想是：

設(shè)存在序列a。

① 如果只有一個(gè)元素，那么最長(zhǎng)上升子序列的長(zhǎng)度為1；

② 如果有兩個(gè)元素，那么如果a[1]>a[0]，則最長(zhǎng)上升子序列的長(zhǎng)度為2，a[1]為該最長(zhǎng)上升子序列的最后一個(gè)元素;若a[1]<a[0]，則最長(zhǎng)上升子序列的長(zhǎng)度為1，a[0]和a[1]均為  其最長(zhǎng)上升子序列的最后一個(gè)元素。

③ 如果由三個(gè)元素，那么如果a[2]>a[0],a[2]>a[1],則a[2]可以作為a[0]或者a[1]所在最長(zhǎng)上升子序列的最后一個(gè)元素。那選擇哪一個(gè)序列就要看a[0],a[1]哪個(gè)所在的序列要更長(zhǎng)。

④ 擴(kuò)展到n個(gè)元素，就是看以a[n]為最后一個(gè)元素的最長(zhǎng)上升子序列的長(zhǎng)度是多少。

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

a存放原始數(shù)據(jù)，b[i]存放的是以a[i]結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度。

代碼如下：

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];   //記錄下元素?cái)?shù)值比a[i]小的但是對(duì)應(yīng)子序列最長(zhǎng)的子序列長(zhǎng)度
        }
      }
       
      b[i]=countmax+1;     //a[i]對(duì)應(yīng)的最長(zhǎng)子序列長(zhǎng)度是
    }
         
  }
   
}

二、出操隊(duì)形

題目描述：

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

輸入：

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

輸出：

對(duì)應(yīng)每個(gè)測(cè)試案例，輸出需要抽出的最少學(xué)生人數(shù)。

樣例輸入：

6

100 154 167 159 132 105

5

152 152 152 152 152

樣例輸出：

0

4

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

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

得到兩個(gè)數(shù)組b1,b2。

b1,b2對(duì)應(yīng)相加再減去重復(fù)的一個(gè)，就是最長(zhǎng)的'山峰'。

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ù)組的最長(zhǎng)上升子序列
 
    b2=reverse.reverse(b2);     //將逆序數(shù)組的最長(zhǎng)上升子序列逆序以便和原始數(shù)組的最長(zhǎng)上升子序列對(duì)應(yīng)相加
     
    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;    //對(duì)應(yīng)相加最長(zhǎng)的再減去重復(fù)的一個(gè)人
    return a.length-max;
  }
}

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

最新評(píng)論