Suponha que haja sequências: 2, 1, 3, 5, descobri que a sequência de ascendência mais longa é 2, 3, 5 ou 1, 3, 5, e o comprimento é 3.
A idéia do algoritmo LIS é:
Suponha que exista uma sequência a.
① Se houver apenas um elemento, o comprimento da sequência ascendente mais longa é 1;
② Se houver dois elementos, se A [1]> a [0], o comprimento da sequência ascendente mais longa for 2, a [1] é o último elemento da sequência ascendente mais longa; Se A [1] <A [0], o comprimento da sequência ascendente mais longa é 1 e a [0] e a [1] são os dois últimos elementos de sua sequência de ascendência mais longa.
③ Se for feito de três elementos, se A [2]> a [0], a [2]> a [1], então a [2] poderá ser o último elemento da sub-sequência ascendente mais longa em que A [0] ou a [1] está localizado. Então, qual sequência escolher depende de qual sequência a [0] e a [1] é mais longa.
④ Para expandir para n elementos, é ver o comprimento da sequência de ascendência mais longa com um [n] como o último elemento.
Definir duas matrizes, uma é a e a outra é b.
a armazena os dados originais, e B [i] armazena o comprimento da sequência de ascendência mais longa que terminou com um [i].
O código é o seguinte:
classe lmax {public static void lmax (int [] a, int [] b) {b [0] = 1; for (int i = 1; i <A.Length; i ++) {int contouMmax = 0; for (int j = 0; j <i; j ++) {if (a [i]> a [j] && b [j]> countMax) {countMax = b [j]; // Registre o comprimento subsequente cujo valor do elemento é menor que um [i], mas corresponde à subseqüência mais longa}} b [i] = countMax+1; // O comprimento subseqüente mais longo correspondente a um [i] é}}}2. Saia da formação
Descrição do título:
Quando no ensino médio, a escola organizou todos os professores e alunos para correr todas as manhãs para se exercitar. Sempre que a ordem de exercício soava, todos começaram a correr no andar de baixo, e então os curtos-alimentos estavam alinhados em frente à linha, enquanto os mais altos estavam alinhados no final da linha. De repente, um dia, a pessoa encarregada da equipe teve uma idéia e queria mudar a formação. Ou seja, quando todos correram do andar superior, todos os alunos foram ocupados aleatoriamente seguidos, e a pessoa encarregada da equipe tirou uma parte dos estudantes da equipe, para que a altura dos alunos restantes da equipe fosse uma forma de "pico" que se levantou primeiro e depois caiu da frente. Dizem que essa forma pode trazer boa sorte a todos, e desejo que todos subam o topo no caminho do aprendizado. (Observe que apenas um lado da montanha atende às condições, como 1, 1, 2, 2 e 1 atende às condições)
digitar:
A entrada pode conter várias amostras de teste.
Para cada caso de teste, a primeira linha inserida é um número inteiro n (1 <= n <= 1000000): representa o número de alunos a serem inseridos.
A segunda linha de entrada inclui n números inteiros: representa a altura do aluno (CM) (um número inteiro positivo com altura não superior a 200).
Saída:
Para cada caso de teste, o número mínimo de alunos a serem desenhados é emitido.
Entrada de amostra:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Saída de amostra:
0
4
Ao usar o LIS para resolver esse problema, você pode considerar o seguinte:
Primeiro, use LIS para encontrar o comprimento da sequência de ascendência mais longa que termina com cada elemento da frente para trás e depois use LIS para encontrar o comprimento da sequência de ascendência mais longa que termina com cada elemento.
Obtenha duas matrizes B1, B2.
B1 e B2 correspondentes à adição correspondente e subtrair a repetida é a 'montanha' mais longa.
classe pública 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]; // Matriz original int [] ar = new int [n]; // scanner de matriz inverso in = new Scanner (System.in); for (int i = 0; i <n; i ++) {a [i] = in.nextInt (); } int [] b1 = new int [n]; @Suppresswarnings ("não utilizado") int [] b2 = new int [n]; Lmax.lmax (a, b1); ar = reverse.versever (a); Lmax.lmax (AR, B2); // Resolva a subsequência ascendente mais longa da matriz inversa b2 = reverse.verse (b2); // inverso a subsequência ascendente mais longa da matriz inversa, a fim de adicionar o correspondente correspondente à subsequência ascendente mais longa da matriz original re = resultado.Result (B1, B2); System.out.print (re); }} <br> <br> <br> <br> Resultado da classe {public static int resultado (int [] a, int [] b) {int max = 0; int [] c = novo 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; // a pessoa correspondente com a adição mais longa e subtraindo o retorno repetido A.Lengthen-max; }}O exposto acima é todo o conteúdo do problema de usar o Java para implementar o algoritmo LIS e fazer formações. Espero que seja útil para todos e apoie mais wulin.com ~