Предположим, что есть последовательности: 2, 1, 3, 5, обнаружите, что самая длинная последовательность восхождения составляет 2, 3, 5 или 1, 3, 5, а длина - 3.
Идея алгоритма LIS:
Предположим, есть последовательность а.
① Если есть только один элемент, то длина самой длинной последовательности воскресения составляет 1;
② Если есть два элемента, если a [1]> a [0], длина самой длинной последовательности восхождения составляет 2, A [1] является последним элементом самой длинной последовательности восхождения; Если a [1] <a [0], длина самой длинной последовательности воскресения составляет 1, а [0] и a [1] - это последние элементы его самой длинной последовательности восхождения.
③ Если он сделан из трех элементов, если a [2]> a [0], a [2]> a [1], то A [2] может быть последним элементом самой длинной подъемной последовательности, где находится [0] или [1]. Затем какая последовательность выбрать зависит от того, какая последовательность A [0] и A [1] длиннее.
④ Чтобы развернуть элементы N, он должен видеть длину самой длинной последовательности восхождения с [n] в качестве последнего элемента.
Определите два массива, один - это, а другой - б.
A хранит исходные данные, а B [I] сохраняет длину самой длинной последовательности воскресения, заканчивающейся [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]; // Записывает длину последующей последовательности, значение элемента которого меньше, чем [i], но соответствует самой длинной последующей последовательности}} b [i] = countmax+1; // самая длинная длина последующей последовательности, соответствующая [i] is}}}2. Выйти из формирования
Описание заголовка:
В старшей школе, школа организовала всех учителей и учеников, чтобы каждый утро бежать, чтобы тренироваться. Всякий раз, когда прозвучал порядок упражнений, все начинали бегать вниз по лестнице, а затем короткие высоты были выровнены перед линией, в то время как более высокие были выровнены в конце линии. Внезапно, однажды, ответственный за команду, придумал идею и хотел изменить формирование. То есть, когда все сбежали с верхнего этажа, все студенты были случайным образом заняты подряд, а человек, отвечающий за команду Говорят, что такая форма может принести удачи всем, и я хочу, чтобы вы все поднялись на вершину на пути обучения. (Обратите внимание, что только одна сторона горы соответствует условиям, например, 1, 1, 2, 2 и 1, соответствует условиям)
входить:
Вход может содержать несколько испытательных образцов.
Для каждого тестового примера первая введенная строка представляет собой целое число n (1 <= n <= 1000000): представляет количество учащихся, которые должны быть введены.
Вторая линия ввода включает в себя n целых чисел: представляет высоту студента (CM) (положительное целое число с высотой не более 200).
Выход:
Для каждого тестового примера минимальное количество учащихся, которые будут нарисованы, является выводом.
Пример ввода:
6
100 154 167 159 132 105
5
152 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 {сканер в = новый сканер (System.in); n = in.nextint (); } while (n <0 || n> 100000); int [] a = new int [n]; // оригинальный массив int [] ar = new int [n]; // Сканер обратного массива в = новый сканер (System.in); for (int i = 0; i <n; i ++) {a [i] = in.nextint (); } int [] b1 = new int [n]; @Suppresswarnings («неиспользованный») int [] b2 = new int [n]; Lmax.lmax (a, b1); ar = reverse.reverse (a); Lmax.lmax (ar, b2); // Решить самую длинную подъемную последующую последующую матрицу b2 = reverse.reeverse (b2); // обратно самая длинная последующая последующая подключаемость обратного массива, чтобы добавить соответствующую соответствующую, соответствующую самой длинной подъемной последующей последовательности исходного массива re = result.result (b1, b2); System.out.print (re); }} <br> <br> <br> <br> Результат класса {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; // соответствующий человек с самым длинным добавлением и вычитает повторный возврат a.length-max; }}Выше приведено все содержание проблемы использования Java для реализации алгоритма LIS и создания формирования. Я надеюсь, что это будет полезно для всех и поддерживать wulin.com больше ~