Description
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
my program
思路：创建一个2*n的二维数组，用来记录到当前字符时，最长递增子序列。可以通过两个嵌套循环操作实现统计结果，然后遍历结果找出最大的即为整个数组的最长递增子序列，时间复杂度是O(n2)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
int res = 1;
vector<vector<int>> ret;
ret.push_back(nums);
ret.push_back(vector<int>(nums.size(), 1));
for (int i = 1; i < nums.size(); i++) {
int max = 1;
for (int j = i - 1; j>=0; j--) {
if (ret[0][j] < ret[0][i] && ret[1][j] >= max) {
max = ret[1][j] + 1;
}
}
ret[1][i] = max;
}
for (int i = 1; i < nums.size(); i++) {
if (ret[1][i] > res)
res = ret[1][i];
}
return res;
}
};Submission Details
24 / 24 test cases passed.
Status: Accepted
Runtime: 29 ms
other
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=0; i < nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}std::lower_bound：Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.
思路：建立最长递增子序列数组。找出当前最长递增子序列数组中第一个大于该数字的，然后替换，如果没有第一个大于该数字的数字，则将其添加到最长递增子序列数组中去。