300. 最长递增子序列

为保证权益，题目请参考 300. 最长递增子序列(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {
        if(nums.size() == 0){
            return 0;
        }


        int len = 1;
        vector<int> d(nums.size() + 1, 0);
        d[1] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > d[len]) {
                len += 1;
                d[len] = nums[i];
            } else {
                int t = bs(d, len, nums[i]);
                d[t] = nums[i];
            }
        }
        return len;
    }

    int bs(vector<int> vec, int len, int target) {
        int l = 1;
        int r = len;
        while (l <= r) {
            int m = (l + r) / 2;
            if (vec[m] >= target) {
                if (m == 1 || (m > 1 && vec[m - 1] < target)) {
                    return m;
                }
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
};

void runTest(){
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(9);
    vec.push_back(2);
    vec.push_back(5);
    vec.push_back(3);
    vec.push_back(7);
    vec.push_back(101);
    vec.push_back(18);

    Solution so;
    cout << so.lengthOfLIS(vec) << endl;
}

int main() {
    runTest();
    return 0;
}

Python

# 300. 最长递增子序列
# https://leetcode-cn.com/problems/longest-increasing-subsequence/

from typing import List


def bs(dp: List[int], num: int):
    l = 0
    r = len(dp) - 1
    while l <= r:
        m = (l + r) // 2
        if dp[m] < num:
            l = m + 1
        else:
            r = m - 1
    return l


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [20000] * (len(nums) + 1)
        for num in nums:
            t = bs(dp, num)
            dp[t] = num

        ans = 0
        for i in range(len(dp)):
            if dp[i] == 20000:
                ans = i
                break
        return ans


if __name__ == "__main__":
    solution = Solution()
    print(solution.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))
    # print(bs([0, 1, 1, 2, 3, 3, 3, 4, 5], 0.5))

解决方案2

CPP

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
    }
};

int main()
{
    return 0;
}