最长上升子序列

const lengthOfLIS = (nums) => {
    if (!Array.isArray(nums)) {
        return 0;
    }
    if (nums.length == 0) {
        return 0;
    }
    let dp = new Array(nums.length);
    dp[0] = 1;
    let maxlen = 1;
    for (let i = 0; i < nums.length; i++) {
        dp[i] = 1;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxlen = Math.max(maxlen, dp[i]);
    }
    return maxlen;
}

贪心算法+二分法

const lengthOfLIS = (nums) => {
    let len = 1,
        n = nums.length;
    if (n == 0) {
        return 0;
    }
    let d = new Array(n + 1);
    d[len] = nums[0];
    for (let i = 1; i < n; ++n) {
        if (nums[i] > d[len]) {
            d[++len] = nums[i]
        } else {
            let l = 1,
                r = len,
                pos = 0;
            while (l <= r) {
                let mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            d[pos + 1] = nums[i]
        }

    }
}

#include <iostream>
#include <vector>

using namespace std;

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

        vector<int> tail;
        tail.push_back(nums[0]);
        // tail 结尾的那个索引
        int end = 0;

        for (int i = 1; i < len; ++i) {
            if (nums[i] > tail[end]) {
                tail.push_back(nums[i]);
                end++;
            } else {
                int left = 0;
                int right = end;
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (tail[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = nums[i];
            }
        }
        return end + 1;
    }
};

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。