Задача о наибольшей возрастающей подпоследовательности — различия между версиями
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | Наибольшая возрастающая подпоследовательность строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le i_j \le n </tex> и <tex> k </tex> - наибольшее из возможных. | + | Наибольшая возрастающая подпоследовательность (''англ''. Longest increasing subsequence - LIS) строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k, 1 \le i_j \le n </tex> и <tex> k </tex> - наибольшее из возможных. |
}} | }} | ||
Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность. | Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность. | ||
Известно несколько алгоритмов решения этой задачи. | Известно несколько алгоритмов решения этой задачи. | ||
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ==== | ==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ==== | ||
Версия 09:31, 27 ноября 2010
| Определение: |
| Наибольшая возрастающая подпоследовательность (англ. Longest increasing subsequence - LIS) строки длины - это последовательность символов строки таких, что и - наибольшее из возможных. |
Задача заключается в том, чтобы отыскать это наибольшее и саму подпоследовательность. Известно несколько алгоритмов решения этой задачи.
