给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
- 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一 : O(n^2)的时间复杂度代码:
思路:(动态规划)
dp[i]表示下标取i的时候,该位置上最长的有序序列长度是多少(只是该位置最长,不一定是整体最长的序列)
在满足nums[i] > nums[j]的情况下,0 <= j < i :
- dp[i] = max(dp[j] + 1);
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
int *dp = new int[nums.size()];
dp[0] = 1;
int max = 1;
for(int i = 1; i < nums.size(); ++i) {
dp[i] = 1;
for(int j = 0; j < i; ++j) {
if(nums[j] < nums[i]) {
int temp = dp[j] + 1;
if(temp > dp[i])
dp[i] = temp;
}
}
max = max > dp[i] ? max : dp[i];
}
return max;
}
};
解法二 :O(nlog 2(n))
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
// dp[i]用来存放长度为i+1的序列最大的一个数值
int *dp = new int[nums.size()];
int max = 1; // 用于记录当前最大的长度
dp[0] = nums[0];
for(int i = 1; i < nums.size(); ++i) {
int start = 0, end = max - 1;
// 先判断两个边界
if(nums[i] < dp[start]) {
dp[start] = nums[i];
continue;
}
if(nums[i] > dp[end]) {
dp[max++] = nums[i];
continue;
}
// 确定是处于当前范围内
while(start <= end) {
int mid = (start + end) / 2;
if(mid > 0 && dp[mid] > nums[i] && dp[mid - 1] < nums[i]) {
// 更新该位置的值,设置为更小的数值,方便后面添加更多大于该位置的值
// eg : 1 2 (4) --> 1 2 (3)
dp[mid] = nums[i];
break;
}
if(dp[mid] > nums[i])
end = mid - 1;
else if(dp[mid] < nums[i])
start = mid + 1;
else // 相等的话没必要更新
break;
}
}
return max;
}
};