Как найти разницу между последним и первым элементом самой длинной увеличивающейся подпоследовательности, так что значение (последний элемент - первый элемент) в LIS является максимум?Самая длинная возрастающая подпоследовательность такая, что последний элемент в LIS максимальный
Давайте используем стандартное решение динамического программирования, в котором мы определяем f[i] как самую длинную возрастающую подпоследовательность, заканчивающуюся в элементе i-th. Мы можем сохранить пару (max length, smallest first element) для каждого i. Можно показать, что это приводит к правильному глобальному решению (интуитивно, это правильно, поскольку оно по-прежнему сохраняет оптимальное решение для всех подпоследовательностей, заканчивающихся в конкретном элементе, и тот факт, что один префикс «лучше», чем другой, означает, что общая подпоследовательность лучше).
Вы также можете сделать это O(N log N), сохранив эти пары в эффективной структуре данных (например, дереве сегментов), если требования к производительности высоки.
Очень наивный алгоритм выглядит следующим образом:
Все это в O (n), это возможно сделать за один проход. Чтобы упростить это, я разбиваю его на два шага.
вопрос не ясен для меня. предположим, что у нас есть 1 100,0,1,2,3,4,5,6, то в чем же ответ? 1,100 или 0,1,2,3,4,5,6 –
@SaeedAmiri здесь ответ должен быть 0,1,2,3,4,5,6 –
@domen пытается с помощью DP soluiton, где при индексе i th он сохраняет значение до тех же самых idex с максимальной длиной и наибольшим значением, заканчивающимся на позиции i th. –