Если вы знакомы с программированием, то наверняка сталкивались с самой длинной убывающей подпоследовательностью или подобными типами вопросов и как-то застревали в подходе этих типов вопросов и разных методах их решения. Но не беспокойтесь, потому что вы получите четкое представление об этих типах вопросов и подходах к их решению в этом блоге. Это одни из самых распространенных типов вопросов, которые задают на любом собеседовании в компании, и их применение также используется в соревновательном программировании. Так или иначе, если вы хотите продолжить программирование, это поможет вам.
Итак, прежде чем перейти непосредственно к подходу, мы сначала поймем некоторые термины, которые часто используются и звучат очень похоже, и студенты могут запутаться.
Последовательность:
Последовательность относится к любому расположению элементов, непрерывному или прерывистому. Последовательность может быть любого порядка, возрастающего или убывающего. Массив также является последовательностью.
Подмассив:
Это также называется подстрокой в случае строки, но они означают то же самое.
Это непрерывная часть массива, что означает, что его можно назвать небольшим массивом, но в непрерывном порядке, что означает, что элементы не могут иметь случайный индекс. Они должны иметь постоянные индексы. Например, предположим, что массив [1,2,3,4,5] тогда [1,2,3] может быть подмножеством, поскольку они непрерывны в родительском массиве, тогда как [1,3,5] не может быть подмассивом. поскольку они не являются непрерывными. Они могут быть пустыми или непустыми.
Последовательность:
Подпоследовательность — это последовательность, которая может быть получена из другой последовательности путем удаления нуля или более элементов. Подпоследовательность следует только одному условию: элементы должны появляться в подпоследовательности в том же порядке, в каком они появляются в исходной последовательности. Между ними могут отсутствовать некоторые элементы, но порядок должен быть таким же. Подпоследовательность, в которой мы не удаляем промежуточные элементы из исходного массива, также называется подмассивом. Поэтому мы можем сделать вывод, что все подмассивы являются подпоследовательностями, тогда как не все подпоследовательности являются подмассивами.
Давайте разберемся с подпоследовательностью на примере. Предположим, массив с элементами [1,2,3,4,5] может иметь как [1,2,3], так и [1,3,5] в качестве подпоследовательности, но не может иметь [1,3,4] в качестве подпоследовательности, как 3 и 4 не следуют первоначальному порядку. Из массива размера n можно составить 2^n-1 подпоследовательностей.
Подпоследовательности также идентичны в случае строк. Давайте возьмем пример строки, чтобы понять это лучше. Предположим, у нас есть строка «coding», тогда «cod» — это и подстрока, и подпоследовательность.
Постановка проблемы:
В этом вопросе нам нужно найти самую длинную убывающую подпоследовательность из заданного массива.
Задача на самую длинную убывающую подпоследовательность состоит в том, чтобы найти подпоследовательность заданной последовательности, в которой элементы подпоследовательности отсортированы от большего к меньшему, и в которой подпоследовательность является максимально возможной. Эта подпоследовательность не обязательно непрерывна или уникальна.
Самая длинная убывающая подпоследовательность с использованием рекурсии
Общий подход к этому вопросу будет заключаться в том, что мы должны найти все подпоследовательности, и среди них мы должны найти все убывающие, а из них мы должны найти ту, которая имеет наибольшую длину. Итак, вот общее предложение: если вы обнаружите какой-либо вопрос, в котором вам нужно найти все, максимум, минимум или нужно пройти всеми возможными способами, помните, что вы можете решить этот вопрос с помощью рекурсии.
Теперь мы увидим рекурсивный подход к этому вопросу. Какой у нас есть выбор при построении подпоследовательности? Что мы можем либо включить текущий элемент в нашу подпоследовательность, либо не включать этот элемент. Но в этом случае у нас есть дополнительное условие, что подпоследовательность должна быть убывающей, поэтому мы будем включать элемент только в том случае, если он меньше предыдущего элемента подпоследовательности, а если нет, то мы не будем включать элемент и повторяться оставшийся массив. И если мы включим элемент, то мы вернем 1+ повторение предыдущих элементов, потому что при включении элемента мы увеличиваем длину подпоследовательности, поэтому мы увеличиваем длину на единицу, но в случае, когда мы не включены, мы просто повторим оставшиеся элементы.
Теперь мы увидим изменения в параметрах и базовом случае. Когда мы сравниваем текущий элемент с предыдущим элементом, т. е. последним элементом текущей подпоследовательности, если текущий элемент больше, чем предыдущий элемент, мы просто повторяем оставшийся массив, ничего не меняя в рекурсивном вызове, кроме изменения индекса для прохождения. Но когда текущий элемент меньше предыдущего, мы рассматриваем его в подпоследовательности, поэтому при рекурсивном вызове, наряду с изменением индекса, мы также обновляем предыдущий элемент нашим текущим элементом, как мы его рассмотрели. И говоря о базовом случае, это будет случай, когда мы достигнем конца массива, и после достижения конца массива мы вернем 0. В этом временная сложность будет экспоненциальной, и она будет использовать стек пространство как пространственная сложность.
Самая длинная убывающая подпоследовательность с использованием мемоизации
Подход запоминания в основном помогает в случае рекурсии, когда у нас есть перекрывающиеся подзадачи. Перекрывающиеся подзадачи означают, что мы снова проходим один и тот же рекурсивный вызов через некоторое время после другого рекурсивного вызова. Итак, в Memoization мы будем хранить результат каждого рекурсивного вызова, и при выполнении любого рекурсивного вызова мы сначала проверяем, существует ли он уже или нет. Если он существует, то мы напрямую возвращаем ответ. Это сэкономит нам много времени. Это изменит временную сложность с экспоненциальной на O(N²). Где N относится к размеру массива, это увеличит сложность пространства на O (N²).
Давайте кратко рассмотрим этот подход. И мы создадим двумерный массив или вектор размером N * N, где N — размер данного массива, и мы инициализируем его значением -1. Где -1 означает, что изначально у нас нет данных ни для одного рекурсивного вызова. И мы передадим этот массив в наш рекурсивный вызов. Перед любым рекурсивным вызовом мы проверяем, не равно ли значение -1, тогда мы вернем это значение, потому что мы уже вычислили ответ для этого значения. После этого остальная часть такая же, как и в рекурсивном коде, только разница, а не простой возврат. Мы сохраним наш ответ в мемоизированном массиве, а затем вернем его.
Самая длинная убывающая подпоследовательность с использованием динамического программирования
Здесь мы обсудим подход к составлению таблиц, в данном случае восходящий подход. Запоминающийся подход работал нормально и значительно снижал сложность, так зачем нам нужен другой подход. Ответ на этот вопрос связан с тем, что пространство стека используется как для мемоизации, так и для обычных рекурсивных вызовов.
В этом подходе мы создадим массив длины, в котором каждый элемент будет хранить длину самого длинного убывающего подмассива, заканчивающегося элементом, присутствующим в текущем индексе основного массива. Первоначально мы инициализируем массив единицей, так как каждый элемент сам по себе является самой длинной убывающей подпоследовательностью. Теперь мы пройдемся по исходному массиву и еще раз проверим все элементы перед ним. Если текущий элемент меньше любого предыдущего элемента, а длина текущего элемента меньше предыдущего элемента, мы увеличиваем длину.
Итак, здесь мы будем использовать два вложенных цикла: один будет проходить от начала к последнему, а другой цикл будет проходить от начального индекса, т.е. 0, к текущему индексу и сверяться с текущим элементом и в соответствии с упомянутым выше условием длина изменится. После успешного обхода обоих циклов нам нужно найти максимальную длину самой длинной убывающей подпоследовательности. Наш массив будет содержать максимальную длину убывающей подпоследовательности, которая заканчивается текущим элементом. Таким образом, мы снова пройдемся по массиву, найдем максимальное значение среди всех значений и вернем его.
