有关递增子序列的几个问题

递增三元子序列

给定一个存放整数的vector，求其是否存在长度为3的递增三元子序列，时间复杂度的要求是O(n)O(n)，空间复杂度的要求是O(1)O(1)。

既然时间复杂度是O(n)O(n)，就要求一遍遍历要得到答案，一种可行解的方式就是，使用两个变量存储三元递增子序列的前两个。设两变量分别为c1、c2，初值设为INT_MAX，设每一次循环取的数是x，若x比c1小，则将c1更新为x，否则判断x是否比c2小，是则更新c2，否则递增三元子序列找到。

bool increasingTriplet(vector &nums) {
    int c1 = INT_MAX, c2 = INT_MAX;
    for (int num : nums) {
        if (num <= c1) {
            c1 = num;
        } else if (num <= c2) {
            c2 = num;
        } else {
            return true;
        }
    }
    return false;
}

算法很巧妙，巧在以下几点：

维护两个变量，保存递增三元子序列的前两个，根据第三个元素来判断，因此只需遍历一遍
当第三个元素的值都比前两个大时，就找到了满足的解
当第三个元素的值比第一个值小，为什么要直接替换第一个元素的值？因为若后面还存在比第一个元素小的两个值，那么当前第三个元素也肯定比那两个值小，也可以构成解
当第三个元素的值介于前两者之间，则更新第二个元素的值，原理同上
最长递增子序列的两种解法

给定一个存放整数的vector，确定其最长递增子序列的长度。常有O(n2)O(n2)和O(nlogn)O(nlogn)两种解法。

时间复杂度O(n2)O(n2)

使用dp[n]来记录以nums[n]结尾的最长递增子序列的长度。代码分为两层循环，外层循环i从1到n-1，更新dp[i]的值;内层循环j从0到i-1,找到最大的dp[j]，用其更新dp[i]。

int lengthOfLIS(vector &nums) {
    int n = nums.size(), ans = 0;
    if (n == 1) return 1;

    vector dp(n, 0);
   
    for (int i = 1; i < n; i++) {
        int k = 0;
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i] && k < dp[j])
                k = dp[j];
        dp[i] = ++k;
        ans = max(ans, dp[i]);
    }
    return ans;
}

时间复杂度O(nlogn)O(nlogn)

这里用到了std::lower_bound函数，此函数返回一个迭代器，指向参数值应该插入的位置。维护一个集合res，遍历一遍vector，每次获得将元素插入改集合的迭代器，若迭代器指向res集合尾部，则将该元素加入res集合，否则直接更新res集合中对应位置的值。
为什么这样可行?其实本质还是让比较小的元素在res集合中，以{10,9,2,5,3,7,101,18}为例，res集合中一开始是{10}，然后是{9}，然后是{2}，然后是{2,5}，然后是{2,3}，然后是{2,3,7}，然后是{2,3,7,101}，最后是{2,3,7,18}。

值得注意的是，这样到最后res集合中并不一定是最长递增子序列的值，但是长度是一样的。

int lengthOfLIS_ex(vector &nums) {
    vector res;
    for (unsigned int i = 0; i < nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if (it == res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}