Leetcode.com, задача №300 (Medium). "Наибольшее возрастающее подмножество". Часть 1.

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru

А данную статью вы можете найти по ссылке

Условие

Дан несортированный массив целых чисел. Найдите длину наибольшего возрастающего подмножества.

Пример

Входной массив: [10, 9, 2, 5, 3, 7, 101, 18]

Ответ: 4

Объяснение: длиннейшие возрастающие подмножества - [2, 3, 7, 101], [2, 5, 7, 18] и [2, 3, 7, 18]; их длины равны 4.

Решение №1. Прямой перебор с рекурсией.

Для использования данного метода нам понадобится перегрузка функции: int LengthofLIS(int[] nums, int prev, int curpos), где nums - входной массив, prev - предыдущее значение элемента массива, curpos - индекс текущего рассматриваемого значения.

public static int LengthofLIS(int[] nums, int prev, int curpos)
{
    if (curpos == nums.Length)
        return 0;
    int taken = 0;
    if (nums[curpos] > prev)
        taken = 1 + LengthofLIS(nums, nums[curpos], curpos + 1);
    int nottaken = LengthofLIS(nums, prev, curpos + 1);
    return Math.Max(taken, nottaken);
}

В теле самой функции в начале проверяем, не вышли ли мы за границу массива. Затем объявляем переменную taken, в которую будет записываться искомая длина возрастающего подмножества.

После этого сравниваем значение элемента массива в текущей позиции (nums[curpos]) со значением предыдущего элемента (prev). Если первое больше второго, то увеличиваем taken на 1 и результат вызова функции LengthofLIS, где предыдущим значением становится nums[curpos], индекс текущего рассматриваемого значения сдвигаем на единицу вперёд. Если же неравенство не выполняется, то переменной nottaken присваиваем результат выполнения функции LengthofLIS, где предыдущее значение оставляется равным prev, а индекс текущего рассматриваемого значения также сдвигается на единицу вперёд.

Таким образом, функция LengthofLIS() возвращает наибольшее значение среди двух чисел: taken и nottaken.

Функция, возвращающая ответ задачи, выглядит следующим образом:

public static int LengthofLIS(int[] nums)
{
    return LengthofLIS(int[] nums, int.MinValue, 0);    
}

Временная сложность: 2 в степени n, именно такой размер у дерева рекурсии.

Пространственная сложность: n * n, т.к. каждый элемент массива перебирается n раз.

Решение №2. Рекурсия с мемоизацией.

Для значительного ускорения времени выполнения запишем результат выполнения каждого рекурсивного вызова в массив. А перед выполнением очередной рекурсии проверим, осуществлялся ли вызов ранее. Если да, то возьмём результат функции из массива.

public static int MemoLengthOfLIS(int[] nums)
{
    int[,] memo = new int[nums.Length, nums.Length];    
    return MemoLengthofLIS(nums, -1, 0, memo);
}

public static int MemoLengthofLIS(int[] nums, int prevIndex, int curpos, int[,] memo)
{
    if (curpos == nums.Length)
        return 0;
    if (memo[prevIndex + 1, curpos] > 0)
        return memo[prevIndex + 1, curpos];
    int taken = 0;
    if (prevIndex < 0 || nums[curpos] > nums[prevIndex])
        taken = 1 + MemoLengthofLIS(nums, curpos, curpos + 1, memo);
    int nottaken = MemoLengthofLIS(nums, prevIndex, curpos + 1, memo);
    memo[prevIndex + 1, curpos] = Math.Max(taken, nottaken);
    return memo[prevIndex + 1, curpos];
}

В первой версии перегруженной функции, возвращающей итоговую наибольшую длину возрастающего подмножества, добавили инициализацию массива для хранения результатов вызова рекурсий.

Во второй версии изменилось назначение второго параметра: теперь вместо значения предыдущего элемента храним его индекс. Это сделано для быстрого перемещения по массиву memo. В теле самой функции появилась проверка на наличие результата выполнения рекурсивной функции:

if (memo[prevIndex + 1, curpos] > 0)
    return memo[prevIndex + 1, curpos];

Если он ненулевой, то из массива сразу выбирается значение длины подмножества, повторных вызовов не происходит.

После нахождения значений переменных taken и nottaken их максимум записывается в memo, и только после этого происходит возврат результата выполнения функции.

Временная сложность: n * n, для каждого элемента происходит перебор всего массива.

Пространственная сложность: n * n, требуется дополнительный массив такого размера.

Ещё больше интересной информации на нашем Telegram канале.