Java를 사용하여 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]이 어느 시퀀스에 더 긴지에 따라 달라집니다.

IV 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,2,1은 모두 조건을 충족합니다.)

입력:

입력에는 여러 테스트 샘플이 포함될 수 있습니다. .
각 테스트 사례에 대해 입력의 첫 번째 줄은 정수 n(1<=n<=1000000)으로, 입력할 학생 수를 나타냅니다.
입력의 두 번째 줄에는 학생의 키(cm)를 나타내는 n개의 정수가 포함됩니다(키는 200 이하의 양의 정수).

출력:

각 테스트 케이스에 맞게 추출해야 하는 최소 학생 수를 출력합니다.

샘플 입력:

6

100 154 167 159 132 105

5

152 152 152 152 152

샘플 출력:

0

4

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>

위 내용은 편집자가 가져온 Java를 사용하여 LIS 알고리즘을 구현하는 문제의 전체 내용이며 PHP 중국어 웹사이트를 지원하는 데 도움이 되기를 바랍니다~

Java를 사용한 LIS 알고리즘 구현 및 구성 구성에 대한 더 많은 관련 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!