LeetCode 300. Longest Increasing Subsequence

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.
Your algorithm should run in O(n2) complexity.

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

update v2.0: //更高效的O(nlogn)方法～
维护一个数组vector<int> v～
将nums[0]加入数组，对于每一个来的数nums[i]，如果大于v.back()，就将它push入数组～
否则，就找到第一个比这个数大的位置，将该位置的数字替换为nums[i]～～
最终返回v数组的长度~~~就是最长字串的长度啦～

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        vector<int> v;
        v.push_back(nums[0]);
        for(int i = 1; i < n; i++) {
            if(nums[i] > v.back()) {
                v.push_back(nums[i]);
            } else {
                *lower_bound(v.begin(), v.end(), nums[i]) = nums[i];
            }
        }
        return v.size();
    }
};

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

int n = nums.size();

if(n == 0)

return 0;

vector<int> v;

v.push_back(nums[0]);

for(int i = 1; i < n; i++) {

if(nums[i] > v.back()) {

v.push_back(nums[i]);

} else {

*lower_bound(v.begin(), v.end(), nums[i]) = nums[i];

}

return v.size();

}

};

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版