编程题 java 递增子序列 动态规划
时间: 2023-07-08 15:33:03 浏览: 48
题目描述:
给定一个无序的整数数组,找到其中最长上升子序列的长度。可以假设所有数字都是不同的,例如:
输入:[10,9,2,5,3,7,101,18]
输出:4
解释:最长的上升子序列是 [2,3,7,101],它的长度是 4。
思路分析:
这道题是一道典型的动态规划问题,可以采用 dp 数组来记录状态。dp[i] 表示以 nums[i] 这个数结尾的最长上升子序列的长度。
具体思路:
1. 初始化 dp 数组的每一个元素为 1,因为每个元素本身就是一个上升子序列。
2. 从左往右遍历数组,对于每个元素 nums[i],再从左往右遍历 nums[0:i-1] 这个范围内的所有元素 nums[j],如果 nums[j] < nums[i],则说明 nums[i] 可以接在 nums[j] 后面形成一个更长的上升子序列,此时更新 dp[i] 的值,即 dp[i] = max(dp[i], dp[j]+1)。
3. 最后遍历一遍 dp 数组,找到其中的最大值,即为最长上升子序列的长度。
Java 代码实现:
```java
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
```
时间复杂度:O(n^2),其中 n 为数组长度。
空间复杂度:O(n),需要一个长度为 n 的 dp 数组来记录状态。