题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

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

方法：动态规划

• 若整数数组 nums 的长度为 1，那么最长递增子序列即为该数字，长度为 1
• 同理，由于 dp[i] 表示 i 及 i 以前的组成的数组所拥有的最长递增子序列的长度，那么应将其初始化为 1 而非之前的 0
• result 表示此时（最终）的最长递增子序列的长度
• 外层循环即为对除第一个数字外的其他数字 i 从前到后的循环，而内层循环为对从第一个数字到 i-1 数字的循环。
  • 若数字 nums[i] 大于此时的 nums[j]，及表示此时的数字 nums[i] 可以同 nums[j] 和与 nums[j] 组成最长递增序列的数字序列结合组成新的递增序列。通过对每个递增序列的长度进行对比，选择最长递增子序列，即得到 dp[i]
  • 每结束一次内层循环，计算一次此时的最长递增子序列的长度 result

class Solution(object):
    def lengthOfLIS(self, nums):
        if len(nums) == 1:
            return 1
        dp = [1] * len(nums)
        result = 0
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
            result = max(result, dp[i])
        return result

参考

代码相关：https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html