本文共 1871 字，大约阅读时间需要 6 分钟。

最长不上升子序列和最长上升子序列是数据处理和算法研究中的经典问题。对于这两个问题，我们可以使用特定的算法来高效解决。

最长不上升子序列的解决方案

不上升子序列（Non-Increasing Subsequence）的目标是找到一个最长的序列，使得序列中的每一个元素都不小于前一个元素。

方法思路

我们可以通过维护一个数组 f 来记录最长不上升子序列的长度。初始化时，f[1] 以第一个元素的负值开始。对于每一个后续元素 a[i]，我们检查是否它小于等于当前长度的最小值。如果是，我们添加它到数组的末尾；如果不是，我们找到它应该插入的位置，然后更新数组中的值。

这个算法的时间复杂度是 O(n log n)，主要是由于 upper_bound 函数的使用，用于快速查找插入位置。

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    vector
      
        a;    int n;    while(~scanf("%d", &a.push_back(n++))) {        n--;        vector
       
         f;        f.push_back(-a[0]);        for (int i = 1; i < n; ++i) {            if (f.back() <= -a[i]) {                f.push_back(-a[i]);            } else {                auto it = upper_bound(f.begin() + 1, f.end(), -a[i]);                f[it - f.begin()] = -a[i];            }        }        cout << f.size() << endl;        f.clear();    }    return 0;}
       
      
     
    
   

最长上升子序列的解决方案

上升子序列（Ascending Subsequence）的目标是找到一个最长的序列，使得序列中的每一个元素都大于前一个元素。

方法思路

类似最长不上升子序列的问题，我们可以使用类似的方法来解决上升子序列问题。我们维护一个数组 f，记录最长上升子序列的长度。初始化时，f[1] 以第一个元素开始。对于每一个后续元素 a[i]，如果它大于当前长度的最大值，我们将其添加到数组的末尾；否则，我们找到它应该插入的位置，更新数组中的值。

该算法的时间复杂度同样是 O(n log n)，主要是由于 lower_bound 函数的使用，用于快速查找插入位置。

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    vector
      
        a;    int n;    while(~scanf("%d", &a.push_back(n++))) {        n--;        vector
       
         f;        f.push_back(a[0]);        for (int i = 1; i < n; ++i) {            if (f.back() < a[i]) {                f.push_back(a[i]);            } else {                auto it = lower_bound(f.begin() + 1, f.end(), a[i]);                f[it - f.begin()] = a[i];            }        }        cout << f.size() << endl;        f.clear();    }    return 0;}
       
      
     
    
   

这两个算法都基于二分查找的思想，通过在数组中查找合适的位置来高效地更新最长子序列的长度，避免了暴力枚举的高时间复杂度。

转载地址：http://vdyhz.baihongyu.com/