题目描述
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example1:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up:
- Could you improve it to O(n log n) time complexity?
解题思路
- 动态规划
- 时间复杂度为(O(n^2))
- 首先dp数组的初始化，都初始化为1，表示本身自增
- 两重循环，第一重循环 i -> nums.size()遍历这个数列，表示更新dp这个数组的值
- 第二重循环，j -> i,表示遍历i之前的数列，遍历的过程中如果nums[i] > nums[j], 则可以用max(dp[i], dp[j] + 1)去更新dp[i]
- 在这个过程中，找一个最大值，即为最后的结果。
C++代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 0;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
if(dp[i] > res){
res = dp[i];
}
}
return res;
}
};
0205解题思路
- 动态规划
- 对于第i个元素，对于 j < i，if(nums[i] > nums[j])，即可以用dp[j] + 1来更新dp[i], 这样一遍一边的扫描，最后即为最大
- 肯定是两重循环
- 有几个注意的点
-
- // int dp[nums.size()] = {1}; // 一维数组初始化 只会有第一个元素为1，其他都初始化为0，这一点也事刚认识到，下次要注意
- // 如果 i 从1 开始，那么当只有1个元素的时候 会错误
C++代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// int dp[nums.size()] = {1}; // 一维数组初始化 只会有第一个元素为1，其他都初始化为0，这一点也事刚认识到，下次要注意
vector<int> dp(nums.size(), 1);
int res = 0;
for(int i = 0; i < nums.size(); i++){ // 如果 i 从1 开始，那么当只有1个元素的时候 会错误
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = max(dp[j] + 1, dp[i]);
}
}
if(dp[i] > res){
res = dp[i];
}
}
return res;
}
};
