nums = [10,9,2,5,3,7,101,18],找到其中最长严格递增子序列的长度,java代码
时间: 2023-09-30 13:02:02 浏览: 33
以下是使用动态规划的 Java 代码实现最长严格递增子序列的长度:
```
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 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);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
```
解释:
1. 定义一个数组 `dp`,其中 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列的长度。
2. 初始化每个元素的子序列长度为 1。
3. 从第 2 个元素开始遍历数组,对于每个元素 `nums[i]`,遍历它之前的元素 `nums[j]`,如果 `nums[j] < nums[i]`,则更新 `dp[i]` 为 `dp[j] + 1`,表示在 `nums[j]` 的最长递增子序列后面加上 `nums[i]` 可以得到以 `nums[i]` 结尾的更长的递增子序列。
4. 每次更新 `dp[i]` 后,都需要更新最长递增子序列的长度 `maxLen`。
5. 遍历完整个数组后,`maxLen` 就是最长递增子序列的长度。
以上是一种基本的动态规划思路,时间复杂度为 $O(n^2)$,如果采用二分查找的优化方法,时间复杂度可以降为 $O(n\log n)$。