给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 用java语言编写。
时间: 2024-03-02 20:53:23 浏览: 28
好的,这是一个经典的动态规划问题,可以使用DP数组来存储子问题的解,以下是Java语言实现:
```java
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; // dp数组用于存储子问题的解
Arrays.fill(dp, 1); // 初始化为1,因为每个数字本身都是一个递增子序列
int maxLen = 1; // 记录最长递增子序列的长度
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) { // 找到小于当前数字的数字,更新dp数组
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]); // 更新最长递增子序列的长度
}
return maxLen;
}
```
这个算法的时间复杂度为 $O(n^2)$,可以使用更高效的算法将时间复杂度优化为 $O(n \log n)$,但是这已经足够解决大多数情况了。
相关问题
7-2 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
这是一道经典的动态规划问题,可以使用动态规划算法来解决。
具体的做法是:定义一个数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化时,将 dp 数组全部初始化为 1,因为每个元素都可以单独成为一个递增子序列。
接下来,遍历数组 nums,对于每个元素 nums[i],再遍历它前面的元素 nums[j],如果 nums[j] 小于 nums[i],则可以将 nums[i] 接到 nums[j] 的后面形成一个更长的递增子序列,此时更新 dp[i] 的值为 dp[j]+1 和 dp[i] 中的较大值。
最后,遍历 dp 数组,找到其中的最大值即为最长递增子序列的长度。
以下是代码实现:
c++给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
这是一个经典的动态规划问题,可以使用 O(n^2) 或者 O(nlogn) 的算法解决。
O(n^2) 的算法思路是定义一个 dp 数组,其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。初始化 dp 数组为 1,即每个元素本身就是一个长度为 1 的严格递增子序列。然后从前往后遍历数组,对于每个位置 i,枚举其前面的所有位置 j,如果 nums[j] < nums[i],则更新 dp[i] = max(dp[i], dp[j] + 1)。
O(nlogn) 的算法思路是使用贪心+二分查找的方法。定义一个 tails 数组,其中 tails[i] 表示长度为 i+1 的严格递增子序列的最后一个元素的最小值。初始化 tails 数组为一个只包含 nums[0] 的数组。然后从第二个元素开始遍历数组,对于每个元素 nums[i],如果 nums[i] > tails[len-1],则将 nums[i] 添加到 tails 数组的末尾,长度加 1;否则在 tails 数组中二分查找第一个大于等于 nums[i] 的位置 j,将 tails[j] 替换为 nums[i]。最终 tails 数组的长度就是最长严格递增子序列的长度。
以下是 O(n^2) 的 C++ 代码实现:
```c++
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
```
以下是 O(nlogn) 的 C++ 代码实现:
```c++
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> tails;
tails.push_back(nums[0]);
for (int i = 1; i < n; i++) {
if (nums[i] > tails.back()) {
tails.push_back(nums[i]);
} else {
int left = 0, right = tails.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (tails[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = nums[i];
}
}
return tails.size();
}
```