给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列 示例 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 提示： 1 <= nums.length <= 2500 -104 <= nums[i] <= 104进阶： 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
解题思路：【动态规划】
dp[i]表示num[i]结尾的最长递增子序列长度dp[i] = max(dp[i], dp[j] + 1)当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。初始化dp[i] = 1
class Solution:def longest_substring_dp(self, nums):length = len(nums)dp = [1] * lengthfor i in range(1, length):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)
if __name__ == '__main__':num = eval(input())solution = Solution()print(solution.longest_substring_dp(num))
仅作为代码记录，方便自学自查自纠
