LeeCode 300. 最长递增子序列（动态规划）

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

动态规划还是找到传递方程，每次还是得想半天。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 1. 递推公式
        # dp[i] = max(dp[k] + [nums[i]]) if 存在k<i且dp[k]的最大值<nums[i]
        # 否则 dp[i] = [nums[i]]

        # 2. 完成条件
        # i = len(nums)-1

        # 3. 边界条件
        # i = 0

        num = len(nums)

        if num == 0:
            return 0
        
        # (最大值, 长度)
        dp = [0]*num

        dp[0] = 1
        res = 1

        for i in range(1, num):
            v = nums[i]

            length_i = 0

            # 找到比nums[i]小的j，且dp[i]最大的，可以考虑优化
            # 参考答案：
            # 新建数组 cell，用于保存最长上升子序列。
            # 如果 cell 中元素都比它小，将它插到最后
            # 否则，用它覆盖掉比它大的元素中最小的那个
            # 保证了最大长度的最大值
            # https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-e/

            for j in range(0, i):

                max_v = nums[j]
                length = dp[j]
                if v > max_v:

                    length_i = max(length_i, length+1)

            if length_i == 0:
                dp[i] = 1
            else:
                dp[i] = length_i
            
            res = max(res, dp[i])
            
            # print(i)
            # print(dp)

        return res