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

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

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

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

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

Условие

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

Пример

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

Ответ: 4

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

Решение №3. Динамическое программирование.

В данном варианте будем использовать метод динамического программирования сверху (простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем). Нам понадобится дополнительный массив dp длиной, равной входному массиву. В его i-й элемент будем записывать наибольшую длину возрастающего подмножества [0 ... i] входного массива. Назовём её length. Расчёт этой длины рассмотрим на примере массива [3, 6, 7, 4, 8, 5].

Для первого элемента, равного 3, length равняется 1. Следовательно массив dp = [1, 0, 0, 0, 0, 0].

Затем берём второй элемент 6. Сравниваем его с первым элементом. 6 > 3, поэтому увеличиваем длину на единицу (length = 2). Записываем её во вторую ячейку массива: dp = [1, 2, 0, 0, 0, 0].

Третий элемент 7.

7 > 3 => length = dp[0] + 1 = 1 + 1 = 2
7 > 6 => length = dp[1] + 1 = 2 + 1 = 3
dp = [1, 2, length = 3, 0, 0, 0]

Четвёртый элемент 4. Если элемент меньше предыдущего, то значение length не меняется.

4 > 3 => length = dp[0] + 1 = 1 + 1 = 2
4 < 6 => length = dp[1] = 2
4 < 7 => length = dp[2] = 3
dp = [1, 2, 3, length = 3, 0, 0]

Пятый элемент 8. Если текущий элемент больше предыдущего, dp[i - 1] меньше или равняется length, то length не изменяем. Это справедливо для случая, когда предыдущее элемент не является наибольшим в подмножестве [0 ... i - 1].

8 > 3 => length = dp[0] + 1 = 1 + 1 = 2
8 > 6 => length = dp[1] + 1 = 2 + 1 = 3
8 > 7 => length = dp[2] + 1 = 3 + 1 = 4
((8 > 4) & (dp[3] = 3) < length)) => length = 4
dp = [1, 2, 3, 3, length = 4, 0]

Шестой элемент 5.

5 > 3 => length = dp[0] + 1 = 1 + 1 = 2
5 < 6 => length = dp[1] = 2
5 < 7 => length = dp[2] = 3
((5 > 4) & ((dp[3] = 3) == length) => length = 3
5 < 8 => length = dp[4] = 4   
dp = [1, 2, 3, 3, 4, 4]

В полученном массиве осталось только найти максимум. Код метода данного решения выглядит так:

public static int DPLengthOfLIS(int[] nums)
{            
    int length = nums.Length;
    if (length == 0)
        return 0;
    int max;
    int[] dp = new int[length];
    for (int i = 0; i < length; i++)
    {
        max = 1;
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j] && dp[j] >= max)
                max = dp[j] + 1;
        }
        dp[i] = max;
    }
    return dp.Max();
}

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

Пространственная сложность: n, т.к. дополнительно создаётся массив dp размерностью n.

Решение №4. Динамическое программирование с помощью бинарного поиска.

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

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

int[] dp = new int[nums.Length], где nums - входной массив

Также объявим переменную, равную количеству найденных элементов подмножества.

int len = 0;

Длина массива dp[] равняется n, но полученное подмножество будет занимать только часть этого массива. Возрастающее подмножество займёт весь массив, только в том случае, если последний - отсортированный массив с наименьшим элементом в самом начале.

Каждый элемент входного массива будем искать с помощью операции бинарного поиска в текущем возрастающем подмножестве:

int i = Array.BinarySearch(dp, 0, len, num), где dp - вспомогательный (отсортированный) 
массив, 0 - начальный индекс диапазона поиска, len - длина диапазона поиска, num - объект, 
который нужно найти.

Функция бинарного поиска вернёт:

индекс элемента в указанном массиве, если элемент найден;

i = Array.BinarySearch({1, 3, 8}, 0, 3, 8) = 2

если параметр num не найден и его значение меньше одного или нескольких элементов массива dp, возвращённое отрицательное число - побитовое дополнение индекса первого элемента, превышающего по значению num;

i = Array.BinarySearch({1, 3, 8}, 0, 3, 2) = -2

Элемент 3 с индексом 1 (array[1] = 3) является первым элементом, превышающим по значению цифру 2 (последний параметр функции бинарного поиска). Побитовое дополнение - это операция инвертирования всех разрядов числа, представленного в двоичной системе счисления, в т.ч. и разряда, отвечающего за знак. Не будем вдаваться в подробности дополнительного кода отрицательных чисел. Заметим только, что в результате получается отрицательное число, уменьшенное на единицу, т.е. результат побитового дополнения индекса 1 будет число -2. Как этой информацией воспользоваться будет описано далее.

если параметр num не найден и его значение больше всех элементов массива dp, возвращённое отрицательное число - побитовое дополнение индекса последнего элемента массива, увеличенного на 1.

Если результат бинарного поиска - отрицательное число, то мы сможем переписать dp[i] таким образом, что значение dp[i] станет меньше, но останется больше значения dp[i-1]. Итоговый код алгоритма:

public static int DPwithBSLengthOfLIS(int[] nums)
{
    int[] dp = new int[nums.Length];
    int len = 0;
    foreach(int num in nums)
    {
        int i = Array.BinarySearch(dp, 0, len, num);
        if (i < 0)
        {
            i = -(i + 1);
        }
        dp[i] = num;
        if (i == len)
        {
            len++;
        }
    }           
    return len;
}

Проиллюстрируем работу алгоритма на примере массива [10, 9, 2, 5, 3, 7, 101, 18]

dp = {0, 0, 0, 0, 0, 0, 0, 0};
len = 0;

num = 10;
i = Array.BinarySearch(dp, 0, 0, 10) = -1
i = -(-1 + 1) = 0;
dp[0] = 10; dp = {10, 0, 0, 0, 0, 0, 0, 0}
len = len + 1 = 1;

num = 9;
i = Array.BinarySearch(dp, 0, 1, 9) = -1
i = -(-1 + 1) = 0;
dp[0] = 9; dp = {9, 0, 0, 0, 0, 0, 0, 0}
len остаётся равным 1;

num = 2;
i = Array.BinarySearch(dp, 0, 1, 2) = -1
i = -(-1 + 1) = 0;
dp[0] = 2; dp = {2, 0, 0, 0, 0, 0, 0, 0}
len = len + 1 = 1;
len остаётся равным 1;

num = 5;
i = Array.BinarySearch(dp, 0, 1, 5) = -2
i = -(-2 + 1) = 1;
dp[1] = 10; dp = {2, 5, 0, 0, 0, 0, 0, 0}
len = len + 1 = 2;

num = 3;
i = Array.BinarySearch(dp, 0, 2, 3) = -2
i = -(-2 + 1) = 1;
dp[1] = 10; dp = {2, 3, 0, 0, 0, 0, 0, 0}
len остаётся равным 1;

num = 7;
i = Array.BinarySearch(dp, 0, 2, 7) = -3
i = -(-3 + 1) = 2;
dp[2] = 7; dp = {2, 3, 7, 0, 0, 0, 0, 0}
len = len + 1 = 3;

num = 101;
i = Array.BinarySearch(dp, 0, 3, 101) = -4
i = -(-4 + 1) = 3;
dp[3] = 101; dp = {2, 3, 7, 101, 0, 0, 0, 0}
len = len + 1 = 4;

num = 18;
i = Array.BinarySearch(dp, 0, 4, 18) = -4
i = -(-4 + 1) = 3;
dp[3] = 18; dp = {2, 3, 7, 18, 0, 0, 0, 0}
len остаётся равным 4;

Ответ - длина наибольшего возрастающего подмножества равна 4.

Временная сложность: n * lg(n), т.к. мы n раз используем двоичный поиск со сложностью lg(n).

Пространственная сложность: n, т.к. дополнительно создаётся массив dp размерностью n.

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