题目的主要信息：

• 对于一个数组，从前往后，每次只能从小到大，问最多经过多少数字
• 即寻找最长递增子序列的长度

方法一：暴力动态规划

具体做法：

要找到最长的递增子序列长度，常用方法是动态规划，$dp\left[i\right]dp[i]$dp[i]表示到元素$ii$i结尾时，最长的子序列的长度，初始化全部为1。

遍历两层，前面的指针$ii$i记录元素，后面指针$jj$j比较与前面的值，若是前面大，理论上$dp\left[i\right]dp[i]$dp[i]需要加上1，但是需要用dp[i]<dp[j]+1判断是否是需要这个$jj$j，若是还有更大的就不需要这个$jj$j。

#include<iostream>
#include<vector>
using namespace std;

int lis(vector<int>& arr) {
    vector<int> dp(arr.size(), 1); //设置数组长度大小的动态规划辅助数组
    int max = 1;
    for(int i = 1; i < arr.size(); i++){
         for(int j = 0; j < i; j++){
            if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1; //i点比j点大，理论上dp要加1
                //但是可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                max = max > dp[i] ? max : dp[i]; //找到最大长度
            }
        }
    }
    return max;
}

int main(){
    int n;
    while(cin >> n){
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入
            cin >> arr[i];
        cout << lis(arr) << endl; //计算最长递增子序列长度
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两层for循环
• 空间复杂度：$O\left(n\right)O(n)$O(n)，辅助数组dp的大小

方法二：二分法动态规划

具体做法：

设置两个辅助数组：dp与len，len起着方法一dp数组的作用，$dp\left[i\right]dp[i]$dp[i]记录以$ii$i结尾的最大递增字符字串，对于每次循环，从后找到比它大的数字，加入dp，若出现第一个不必dp中最后一位数大的，则需要使用二分查找，对剩下部分找第一个大于dp中最后一位的，再将其加入。由此，方法一中的第二个循环就变了一个$lo{g}_{2}nlog\_2n$log2​n的二分查找。

#include<iostream>
#include<vector>
using namespace std;

int biSearch(int x, vector<int>& dp){  //二分查找函数
    int left = 0, right = dp.size(), mid;
    while(left <= right){
        mid = (right + left) / 2;
        if(dp[mid] >= x)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}
int lis(vector<int>& arr) {
    vector<int> len; //设置数组长度大小的动态规划辅助数组
    vector<int> dp;//用于二分划分的辅助数组
    dp.push_back(arr[0]);
    len.push_back(1);
    for(int i = 1; i < arr.size(); i++){
         if(arr[i] > dp[dp.size() - 1]) { 
             dp.push_back(arr[i]);
             len.push_back(dp.size());
         }
         else{
             int t = biSearch(arr[i], dp); //二分查找，找到第一个大于arr[i]的dp位置
             dp[t] = arr[i];
             len.push_back(t + 1);
        }
    }
    return dp.size();
}

int main(){
    int n;
    while(cin >> n){
        vector<int> arr(n);
        for(int i = 0; i < n; i++) //输入
            cin >> arr[i];
        cout << lis(arr) << endl; //计算最长递增子序列长度
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，遍历一次，每次的二分查找为$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，借助了辅助空间dp与len