[LeetCode 300] Longest Increasing Subsequence

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(n2) complexity.

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

 

分析

这道题可以使用动态规划来做，使用vector<int> dp记录当前dp[i] 表示当前i-end的最长的长度。从后向前进行遍历。

这道题也有一个n*log n的方法，就是使用二分查找的办法。使用set<int>来简化二分查找，当从前到后遍历数组，在set中寻找nums[i]所处的位置iter，如果iter == s.end()，表明nums[i] 比set中的数字都要大，则直接插入nums[i]。如果iter != s.end()， 表明nums[i]在已经找到的增序列的中间，此时把iter 的数字替换为nums[i]，这样既不会影像当前的增序列的长度，也更新了nums[0] - nums[i]中的增序列。最后返回最终set的size即可。

Code

动态规划

class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() == 0) return 0; int maxLen = 1; vector<int> dp(nums.size(), 1); dp[0] = 1; for (int i=1; i < nums.size(); i ++) { for (int j=0; j < i; j ++) { if (nums[i] > nums[j]) { dp[i] = max(dp[j] + 1, dp[i]); maxLen = max(dp[i], maxLen); } } } return maxLen; } };

二分查找

class Solution { public: int lengthOfLIS(vector<int>& nums) { int res = 0; int len = nums.size(); set<int> s; for (int i = 0; i < nums.size(); i ++) { set<int>::iterator iter = s.lower_bound(nums[i]); if (iter == s.end()) { s.insert(nums[i]); continue; } else { s.erase(iter); s.insert(nums[i]); } } return s.size(); } };

运行效率

二分查找

Runtime: 4 ms, faster than 98.29% of C++ online submissions for Longest Increasing Subsequence.

Memory Usage: 9.4 MB, less than 5.00% of C++ online submissions forLongest Increasing Subsequence.