最长上升子序列

如果是连续序列，只需要扫描一遍。但因为这里子序列可能不连续，需要动态规划

方法1

比较直观的想法，就是用dp维护以某一个元素结束的LIS长度。假设dp[1, …, i - 1]已知，要求dp[i]，即以第i个元素结束的LIS长度，则可以遍历前i-1个元素（标号j），且作如下判断：

• 如果a[j] < a[i], 则说明第i个元素可以接在dp[j]对应的LIS后面，形成一个dp[j] + 1长度的上升序列。找到这样的j并取最大的长度即可。
• 如果没有这样的j，dp[i]为1

即转移为dp[i] = max(dp[j] + 1) where a[j] < a[i] for j in 1 .. i - 1

复杂度是$O(n^2)$的。

方法2

换一种思路，还是用一个dp数组，但是dp[i]表示的是所有长度为i的上升序列的末尾元素的最小值。我们再用len表示当前找到的LIS的长度。这样，我们遍历原始数据，当遍历到a[i]时：

• 如果dp[len] < a[i], 把a[i]接在长度为len的序列后面，就形成长度为len+1的上升序列，即dp[++len] = a[i]
• 否则，在dp[1, len]里找到第一个大于等于a[i]的元素，假设是d[j]。因为d[j]之前的元素都比a[i]小，所以a[i]不能替换任何一个，而d[j]后面的元素也不能替换，否则不满足上升序列的要求。所以只有d[j]能被替换。将a[i]替换到d[j]，这样长度为j的上升序列的末尾元素不变或者变小了。

用STL lower_bound 可以方便的实现

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0;
            int* d = new int[n];
            d[0] = nums[0];
            int len = 1;
    
            for (int i = 1; i < n; ++i) {
                int ele = nums[i];
                if (ele > d[len - 1]) {
                    d[len++] = ele;
                } else {
                    *lower_bound(d, d + len, ele) = ele;
                }
            }
    
            return len;
        }
    };

复杂度$O(nlogn)$

相关

第二种办法也可应用于类似的情况，比如最长不下降子序列。此时要找的是第一个大于a[i]的元素，用upper_bound实现

第一种办法也有价值，可以稍微改造后算出LIS的个数。比如673. 最长递增子序列的个数

参考

• 300. 最长上升子序列 - 力扣（LeetCode）
• 最长不下降子序列nlogn算法详解 - lvmememe - 博客园