LeetCode300. Longest Increasing Subsequence（动态规划）

LeetCode300. Longest Increasing Subsequence（动态规划）

• Medium
• Accepted：207,426
• Submissions：512,883

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

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(n^2)$ complexity.

Follow up: Could you improve it to $O(nlog n)$ time complexity?

链接

https://leetcode.com/problems/longest-increasing-subsequence

代码

• Runtime: 40 ms, faster than 53.08% of C++ online submissions for Longest Increasing Subsequence.
• Memory Usage: 8.7 MB, less than 47.63% of C++ online submissions for Longest Increasing
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) // 考虑空串
return 0;
vector <int> dp(n + 1, 1);
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
}
int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, dp[i]);
return ans;
}
};
• Runtime: 8 ms, faster than 75.08% of C++ online submissions for Longest Increasing Subsequence.
• Memory Usage: 8.5 MB, less than 92.37% of C++ online submissions for Longest Increasing Subsequence.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) // 考虑空串
return 0;
vector <int> low;
for (int i = 0; i < n; ++i)
{
// low中大于等于nums[i]的第一个位置
auto it = lower_bound(low.begin(), low.end(), nums[i]);
if (it == low.end()) // nums[i]大于low中所有元素，直接加上
low.push_back(nums[i]);
else // 修改为nums[i]
*it = nums[i];
}
return low.size();
}
};

The end.
2019年4月7日 星期日