1. question: 最长递增子序列(中等)
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-increasing-subsequence
示例 1:
1 | 输入:nums = [10,9,2,5,3,7,101,18] |
示例 2:
1 | 输入:nums = [0,1,0,3,2,3] |
示例 3:
1 | 输入:nums = [7,7,7,7,7,7,7] |
提示:
1 | 1 <= nums.length <= 2500 |
2. answers
这道题最开始做没想出来思路,参考题解。本体的局部最优解不一定是全局最优解,因为子序列中各个元素有了大小顺序。所以说第i个元素结尾的子数组的最长子序列要和前面所有【最后一个元素小于当前元素】的子数组形成的最长子序列比较,取最大值。
以动态规划的角度来看,其实本题的状态转移,前面所有小于当前元素的子数组的子序列都可转移过来。因此,在比较的时候应该比较所有的子序列,判断最长长度。
定义数组dp[i]表示以当前元素结尾的最长子序列的长度。
定义数组dp[i]表示以数组中第i个元素结尾形成的子数组所形成的最长子序列的元素个数。显然由以下状态得到:
- dp[0]
- dp[1]
- dp[2]
- dp[3]
- …
- dp[i-1]
比较取最大值即可,注意,加上本元素数量1。代码如下所示:
1 | public class Solution_0136 { |
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。