1.题目描述:
给你一个整数数组nums,找到其中最长严格递增子序列的长度 。子序列是由数组派生而来的序列,删除或不删除数组中的元素而不改变其余元素的顺序 。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列 。
2.动态规划:
dp[i]代表以i索引位置结尾前面的最长递增子序列,dp[i]的推导则需要遍历其前面所有dp元素,如果i索引位置的元素较大则取前面最大值+1 。代码如下,详细见注释:
class Solution {public int lengthOfLIS(int[] nums) {//if (nums.length == 1) return 1;int[] dp = new int[nums.length];int max = 1;dp[0] = 1;for (int i = 1; i < dp.length; i++) {dp[i] = 1;//初始化为1,可以放在外面初始化for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(max, dp[i]);}return max;}} 【leetcode300. 最长递增子序列】进阶:待更新 。。。
- 春季老年人吃什么养肝?土豆、米饭换着吃
- 三八妇女节节日祝福分享 三八妇女节节日语录
- 老人谨慎!选好你的“第三只脚”
- 校方进行了深刻的反思 青岛一大学生坠亡校方整改校规
- 脸皮厚的人长寿!有这特征的老人最长寿
- 长寿秘诀:记住这10大妙招 100%增寿
- 春季老年人心血管病高发 3条保命要诀
- 眼睛花不花要看四十八 老年人怎样延缓老花眼
- 香槟然能防治老年痴呆症? 一天三杯它人到90不痴呆
- 老人手抖的原因 为什么老人手会抖
