给你一个整数数组 nums ,找到其中最长严格递增子序列的长度.
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3627] 是数组 [0316227] 的子序列.
输出:4
这又5是一道动态规划题,是子序列系列问题的入门题,仍是抓住三个要点:
dp[i]:考虑前 i 个元素,以第 i 个数字结尾的最长上升子序列的长度.
需要把第 i 个元素考虑进去,即假设nums=[123],dp[2]表示从下标0到下标2的最长上升子序列,很显然等于3.
参考力扣官方解析中的动画演示能更好理解.
需要二层循环,外层假设nums[i]为子序列的最后一个元素,内层假设nums[j]为子序列的第一个元素,结合dp[i]的定义,就能得到最长度.
虽然是入门子序列的问题,但对我而言仍是秃头难想得出的,理解答案已经有点难了,还需要不断的记忆相关类型的套路才行.