Хитрый LIS. Разбор задачи 300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

LIS - Longest Increasing Subsequence. Наибольшая возрастающая последовательность.

Дан массив чисел nums. Верните длину наиболее длинной строго возрастающей подпоследовательности.

Подпоследовательность - это последовательность элементов полученная из другой последовательности путем удаления нескольких (возможно нуля) элементов с сохранением порядка.например, последовательность [1, 2, 3, 4, 5]:подпоследовательности: 1, 2, 3, 4, 5 (удалили 0 элементов)1,3,5 - (удалили 2 и 4)

Пример 1:

Ввод: nums = [10,9,2,5,3,7,101,18]
Вывод: 4
Объяснение: Наибольшая строговозрастающая последовательность [2,3,7,101], 
таким образом длина 4.

Пример 2:

Ввод: nums = [0,1,0,3,2,3]
Вывод: 4

Пример 3:

Ввод: nums = [7,7,7,7,7,7,7]
Вывод: 1

Решение

Заведем массив dp (dynamic programming).
Определим, что мы будем в нём хранить.
Договоримся, что мы будем хранить в dp[i] длину максимальной строговозрастающей подпоследовательности, если бы у нас было только i элементов, тогда ответ будет dp[dp.Length - 1] (или более кратко dp[^1]).
Например:
nums = [5, 6, 7, 1, 2]
dp = [1, 2, 3, 3, 3]

nums = [5, 6, 1, 2, 3]
dp = [1, 2, 2, 2, 3]

Мы могли бы договориться, хранить в dp[i] длину максимальной 
строговозрастающей подпоследовательности, которая оканчивается элементом 
nums[i] и тогда было бы так
nums = [5, 6, 7, 1, 2]
dp = [1, 2, 3, 1, 2]

nums = [5, 6, 1, 2, 3]
dp = [1, 2, 1, 2, 3]
Тогда ответ был бы в dp.Max();

Определим базовый случай:
dp[0] = 1 - если бы у нас был только один элемент он бы и составлял максимальную подпоследовательность размера 1.

Теперь определимся, как вычислять dp[i].
В нашем случае может показаться, что если nums[i] > nums[i - 1],
то dp[i] = dp[i - 1] + 1, но это не так.

возьмем последовательность 5, 6, 7, 1, 2
здесь 2 больше 1, а dp[3] == 3 (у нас в dp[3] должна храниться максимальная длина, как если бы у нас было бы только числа [5, 6, 7, 1], т.е. 3).

то есть, чтобы вычислить dp[i] нам нужно найти длины всех последовательностей, оканчивающейся элементом меньше чем nums[i], и из них выбрать максимальную.

Заведем второй массив dp2. В dp2[i] будем хранить максимальную длину строговозрастающей последовательности, которая оканчивается элементом nums[i].

Пока код такой:

public class Solution {
    public int LengthOfLIS(int[] nums) {
        //dp[i] - длина максимальной строговозрастающей последовательности,
        //если бы у нас было i элементов.
        var dp = new int[nums.Length];
        //dp2[i] - длина максимальной строговозрастающей последовательности,
        //оканчивающийся элементом nums[i].
        var dp2 = new int[nums.Length];
        dp[0] = 1;
        dp2[0] = 1;
        for (var i = 1; i < dp.Length; i++)
        {
            var maxSeq = 1;
            //идём назад и ищем элемент меньше текущего.
            for (var j = i - 1; j >= 0; j--)
            {
                if (nums[j] < nums[i])
                {
                    //нашли. тогда длина строговозврастающей
                    //последовательности - это длина которая оканчивается
                    //элементом nums[j] (то есть значение dp2[j]) плюс 1.
                    maxSeq = Math.Max(maxSeq, dp2[j] + 1);
                }
            }
            dp2[i] = maxSeq;
            dp[i] = Math.Max(dp[i - 1], maxSeq);//максимальная длина
            //оканчивающиейся элементом nums[i], необязательно максимальная
            //длина вообще
            //nums =[5,6,7, 1, 2]
            //dp2 =[1, 2, 3, 1, 2]
            //dp = [1, 2, 3, 3, 3]
        }
        return dp[^1];
    }
}

Если мы посмотрим, то увидим, что из массива dp в итерациях нужен только последний элемент (dp[i] и предыдущий dp[i - 1]).
мы можем заменить его на одну переменную. Назовем её макс, а массив dp2
переименовать в массив dp.

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var max = 1;//вместо массива dp
        var dp = new int[nums.Length];//бывший массив dp2
        dp[0] = 1;
        for (var i = 1; i < dp.Length; i++)
        {
            var maxSeq = 1;
            for (var j = i - 1; j >= 0; j--)
            {
                if (nums[j] < nums[i])
                {
                    maxSeq = Math.Max(maxSeq, dp[j] + 1);
                }
            }
            dp[i] = maxSeq;
            max = Math.Max(max, maxSeq);
        }
        return max;
    }
}

Если бы мы сразу договорились хранить в dp[i] длину максимальной строговозрастающей последовательности, оканчивающейся элементом nums[i],
мы бы могли сразу перейти к такому решению.