Как доказать правильность следующего алгоритма

Question

Проблема заключается в том, чтобы найти LIS (самая длинная возрастающая подпоследовательность) любого заданного массива. Пример. а [] = {10,9,7,8,9}; длина = 3; {7,8,9}

Так один из способов сделать в NlogN является

1. Сортировка массива
2. Возьмите ЛСК двух , причиненный в результате является LIS.

Теперь я понял, как это сделать. Но как я могу доказать, что это правильно. Как подать заявку здесь?

Answer 1

В вашем случае нет необходимости для индукции, вы должны показать три вещи:

• полученного метод захватывает возрастающая последовательность - приходит непосредственно из того, что она является частью отсортированного массива
• в результате подпоследовательность существует во входном массиве - поступает непосредственно из определения LCS (common подпоследовательности)
• больше не увеличивается подпоследовательность - вы можете легко показать, что самая длинная последовательность должна присутствовать в обеих входных последовательностях (по определению) и в отсортированном массиве s o он также будет анализироваться LCS, поэтому он не может быть длиннее, чем тот, который возвращается LCS.