300-longest-increasing-subsequence.md

300. Longest Increasing Subsequence - 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n²) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

---

题目标签：Binary Search / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

可以使用动态规划。dp数组记录以当前数字结束的最长上升子序列长度。对于每个数字nums[i]，查看其左侧比它小的数字nums[j]，状态转移方程：dp[i] = max(dp[i], 1+dp[j])。时间复杂度O(N^2)

二分法。维护一个数组rec，该数组第i个元素记录长度为i+1的上升子序列末端最小数字。对于每个数字num，与该数组末端的数字back进行比较，如果num > back，则将num加入该数组rec的末端；否则，在数组rec中二分查找最小的比num大的元素，并以num替换之。最后，最长上升子序列的长度就是rec的长度。

Language	Runtime	Memory
cpp	0 ms	8.8 MB

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (!nums.size()) return 0;
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > ret.back()) 
                ret.push_back(nums[i]);
            else
                ret[lower_bound(ret.begin(), ret.end(), nums[i]) - ret.begin()] = nums[i];
        }
        return ret.size();
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();