Suppose there are sequences: 2, 1, 3, 5, find that the longest ascender sequence is 2, 3, 5 or 1, 3, 5, and the length is 3.
The idea of LIS algorithm is:
Suppose there is a sequence a.
① If there is only one element, then the length of the longest ascender sequence is 1;
② If there are two elements, if a[1]>a[0], the length of the longest ascender sequence is 2, a[1] is the last element of the longest ascender sequence; if a[1]<a[0], the length of the longest ascender sequence is 1, and a[0] and a[1] are both the last elements of its longest ascender sequence.
③ If it is made of three elements, if a[2]>a[0], a[2]>a[1], then a[2] can be the last element of the longest ascending sub-sequence where a[0] or a[1] is located. Then which sequence to choose depends on which sequence a[0] and a[1] is longer.
④ To expand to n elements, it is to see the length of the longest ascender sequence 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 ascender sequence 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]; //Record the subsequence length whose element value is smaller than a[i] but corresponds to the longest subsequence} } b[i]=countmax+1; //The longest subsequence length corresponding to a[i] is } } }2. Go out of the formation
Title description:
When in high school, the school organized all teachers and students to run every morning to exercise. Whenever the exercise order sounded, everyone started running downstairs, and then the short-heighted ones were lined in front of the line, while the taller ones were lined at the end of the line. Suddenly, one day, the person in charge of the team came up with an idea and wanted to change the formation. That is, when everyone ran down from the upper floor, all the students were randomly occupied in a row, and the person in charge of the team took out a part of the students from the team, so that the height of the remaining students in the team was a "peak" shape that rose first and then fell from the front. It is said that such a shape can bring good luck to everyone, and I wish you all to climb the top on the road of learning. (Note, only one side of the mountain meets the conditions, such as 1, 1, 2, 2, and 1 meets the conditions)
enter:
The input may contain multiple test samples.
For each test case, the first line entered is an integer n(1<=n<=1000000): represents the number of students to be entered.
The second line of input includes n integers: represents the student's height (cm) (a positive integer with height not higher than 200).
Output:
For each test case, the minimum number of students to be drawn is output.
Sample input:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Sample output:
0
4
When using LIS to solve this problem, you can consider this:
First, use LIS to find the length of the longest ascender sequence ending with each element from front to back, then use LIS to find the length of the longest ascender sequence ending with each element.
Get two arrays b1, b2.
b1 and b2 corresponding to the corresponding addition and subtracting the repeated one is the longest 'mountain'.
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]; //Original array int []ar = new int[n]; //Inverse array 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); //Solve the longest ascending subsequence of the inverse array b2=reverse.reverse(b2); //Inverse the longest ascending subsequence of the inverse array so as to add the corresponding corresponding to the longest ascending subsequence of the original array 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; //The corresponding person with the longest addition and subtracting the repeated return a.length-max; }}The above is all the content of the problem of using Java to implement LIS algorithm and making formations. I hope it will be helpful to everyone and support Wulin.com more~