자바를 사용하여 LIS 알고리즘을 실현하고 대형을 조작하는 문제

가령 서열이 있다고 가정하면 2, 1, 3, 5, 가장 긴 상승 서열을 구하면 2, 3, 5 또는 1, 3, 5이고 길이는 모두 3이다.
LIS 알고리즘은 다음과 같습니다.
시퀀스 a를 설정합니다.
① 원소가 하나만 있다면 가장 긴 상승 서열의 길이는 1이다.
② 만약 두 개의 원소가 있다면 a[1]>a[0]라면 최장 상승 서열의 길이는 2이고 a[1]는 이 최장 상승 서열의 마지막 원소이다.만약에 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]로 끝나는 가장 긴 상승 서열의 길이를 저장한다.
코드는 다음과 같습니다.


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] 
    }
         
  }
   
}

2. 출조대형
제목 설명:
고등학교에 다닐 때 매일 아침 학교에서 전교의 교사와 학생을 조직하여 달리기를 해서 신체를 단련해야 했다. 체조령이 울릴 때마다 모두들 아래층으로 달리기 시작했다. 그리고 키가 작은 사람은 대열의 앞에 서고 키가 높은 사람은 대열의 끝에 서야 했다.갑자기 어느 날 체조 담당자가 하나의 생각을 했다. 대형을 바꾸려고 했다. 바로 모두가 위층에서 뛰어내린 후에 모든 학생들이 무작위로 한 줄을 차지한 다음에 체조 담당자가 대열에서 일부 학생을 뽑아서 대열에 남은 학생들의 키는 앞뒤로 보면 먼저 높아지고 나중에 떨어지는'산봉우리'모양이다.이런 형상이 모두에게 행운을 가져다 줄 수 있다고 하니 모두가 공부하는 길에서 용감하게 정상에 오르기를 축원합니다.(주, 산봉우리는 한쪽만 있어도 조건에 부합된다. 예를 들어 1, 1, 2, 1은 모두 조건에 부합된다)
입력:
입력은 여러 개의 테스트 샘플을 포함할 수 있습니다.
모든 테스트 사례에 대해 입력한 첫 줄은 정수 n(1<=n<=1000000): 입력할 학생의 개수를 대표합니다.
입력한 두 번째 줄은 n개의 정수를 포함한다. 학생의 키(cm)를 대표한다(200보다 크지 않은 정수).
출력:
각 테스트 사례에 대응하여 추출해야 할 최소 학생 수를 수출한다.
샘플 입력:
육
100 154 167 159 132 105
오
152 152 152 152 152
샘플 출력:
0
사
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;
  }
}

지금까지 여러분에게 자바를 사용하여 LIS 알고리즘을 실현하고 대형을 구성하는 문제의 전체 내용입니다. 여러분께 도움이 되고 많은 응원 부탁드립니다~

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Java/Excel에 아래 첨자 및 위 첨자 삽입

위 첨자 및 아래 첨자는 기준선 위 또는 아래에 입력되는 소문자 또는 숫자입니다. 일반적으로 각주, 참조, 수학 및 화학 기호에 사용됩니다. 이 기사에서는 Java용 Free Spire.XLS를 사용하여 프로그래밍 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

자바를 사용하여 LIS 알고리즘을 실현하고 대형을 조작하는 문제

좋은 웹페이지 즐겨찾기