最长递增子序列
发布时间
阅读量：
阅读量
最长自增子序列
题目
给你一个整数数组 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 \\ -10^4 <= nums[i] <= 10^4
问题分析
根据题目可以得到三个条件
- 最长
- 递增
- 子序列
根据上图可以理解本题的意思
思路
利用动态规划的思想，自底向上 的进行求解。
设计状态
可以定义一个数组dp[i]，表示以i结尾的最长递增子序列的长度为dp[i]
初始状态
对于每一个数来说，它自己可以单独成为一个递增的子序列，所以，数组初始化都为1
状态转移
那么对于dp[i]来说，dp[i]的值是怎么得到的呢？
首先，dp[i]肯定是在从自己开始（也就是dp[i] = 1) 和前一个递增的数的长度进行比较，选取最大值。
那么问题在于如何找到这所谓的前一个递增的数呢？
对于i而言，可以从第一个数遍历到 i - 1 个数，在从中与 dp[i] 进行比较，选择小的 dp[j] 进行 +1 ，这样便能够实现递增子序列长度的增加了。
根据以上动画能够理解上面所说的思路了
返回最终的解
在实现了 dp[i] 之后，就可以通过遍历数组求去最大值，该最大值便是最长递增子序列的长度
代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[2510];
Arrays.fill(dp, 1); // 初始化都为1
int _max = 1; // 定义变量存取最长的长度
for (int i = 1; i < nums.length; i++) {
// 从第一个数开始逐个比较
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) { // 小于 即是递增的
// 执行状态转移
dp[i] = Math.max(dp[i], dp[j] + 1);
// 记录最大值
_max = Math.max(_max, dp[i]);
}
}
}
// 返回最终的解
return _max;
}
}全部评论 (0)
还没有任何评论哟~