Use java to implement LIS algorithm and solve the problem of formation formation

Assume there is a sequence: 2,1,3,5. The longest ascending subsequence is 2,3,5 or 1,3,5, both of which have a length of 3.

The idea of ​​LIS algorithm is:

Suppose there is sequence a.

① If there is only one element, then the length of the longest ascending subsequence is 1;

② If there are two elements, then if a[1]>a[0], then The length of the longest ascending subsequence is 2, and a[1] is the last element of the longest ascending subsequence; if a[1]e7650d9aed29da546653f73e6f21b55ea[0], a[2]>a[1], then a[2] can be used as a[0] or a The last element of the longest ascending subsequence where [1] is located. Which sequence to choose depends on which sequence a[0] or a[1] is located in is longer.

④ Expanding to n elements is to see the length of the longest ascending subsequence with a[n] as the last element.

Define two arrays, one is a and the other is b.

a stores the original data, and b[i] stores the length of the longest ascending subsequence ending with a[i].

The code is as follows:

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. Exercise formation

Title description:

When I was in high school, the school had to organize the whole school’s teachers every morning Students run to exercise. Whenever the order is sounded, everyone starts running downstairs. Then the short ones line up at the front of the line, and the taller ones line up at the back. Suddenly, one day the person in charge of the exercise came up with an idea and wanted to change the formation. After everyone ran down the stairs, all the students were randomly placed in a row, and then the person in charge of the exercise was drawn from the team. For some students, the height of the remaining students in the team looks like a "peak" shape when viewed from front to back. It is said that this shape can bring good luck to everyone, and I wish you all the best in your studies. (Note, only one side of the mountain meets the conditions, such as 1,1,2,2,1 all meet the conditions)

Input:

The input may contain multiple test samples.
For each test case, the first line of input is an integer n (1<=n<=1000000): representing the number of students to be input.
The second line of input includes n integers: representing the student's height (cm) (the height is a positive integer not higher than 200).

Output:

Corresponding to each test case, output the minimum number of students that need to be extracted.

Sample input:

6

100 154 167 159 132 105

5

152 152 152 152 152

Sample output:

0

4

When using LIS to solve this problem, you can think about it this way:

First of all, once upon a time Use LIS backwards to find the length of the longest ascending subsequence ending with each element, then reverse the order of the array, and then use LIS to find the length of the longest ascending subsequence ending with each element.

Get two arrays b1 and b2.

The corresponding addition of b1 and b2 and then subtraction of the repeated one is the longest 'peak'.

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

The above is the entire content of the problem of using java to implement LIS algorithm and formation formation brought by the editor. I hope it will be helpful to everyone. Please support the PHP Chinese website~

For more articles related to using java to implement LIS algorithm and formation formation, please pay attention to the PHP Chinese website!