题解 | #最长上升子序列(一)#

解题思路1：

• 首先搞清楚几个问题，到结尾点的最长上升子串应该思考成为，不是以结尾下表i结尾的子串。但是需要知道以i结尾的子串的长度。最终只要取出其中以某个点为结尾的最大长度子串就是要求的答案。
• 递归的思维方式来解决此题，求以最后结尾点i为结束的子串长度$dp[i]dp[i]$只要比较节点$0\mathrm{～}i-10\; ～i-1$中是否存在$v[i]>v[j]v[i]\; >\; v[j]$ （其中）,利用$mxmx$记录符合条件的最大长度，如果存在即当前点为结尾的最大长度$dp[i]=mx+1dp[i]\; =\; mx+1$。
• 最后遍历整个数组。取出最大值输出

#include<bits/stdc++.h>
using namespace std;
int solve( int i, vector<int> &v, vector<int> &dp){//递归的写法
    if(dp[i] != 0) return dp[i];
    if (i == 0) dp[i] = 1;
    else{
        int mx = 0;
        for(int j = 0; j < i; ++j){
            int tmp = solve(j, v, dp);//坑点，此处必须先有值，再比较，否则就挂了。吐血的坑写法：if(v[i] > v[j]) mx = max(solve(j, v, dp), mx);
            if(v[i] > v[j]) mx = max(tmp, mx);
        }
        dp[i] = mx + 1;
    }
    return dp[i];
}
void solve2(int n, vector<int> &v, vector<int> &dp){//递推的写法
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        int mx = 0;
        for(int j = 0; j < i; ++j){
            if (v[i] > v[j]) 
                mx = max(dp[j], mx);
        }
        dp[i] = mx+1;
    }
}
int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i){
        cin>>arr[i];
    }
    vector<int> dp(n);
    solve(n-1, arr, dp);
    // solve2(n, arr, dp);
    int res = 0;
    for(auto i : dp){
        res = max(res, i);
    }
    cout<<res<<endl;
    return 0;
}

解题思路2：

• 上述解法时间复杂度$O(n^2)O(n^2)$，在数据量超过$10^{5}10^5$的时候就不够快了。
• 这题可以有$O(n\log n)O(n\; \backslash log\; n)$做法
• 领$dpdp$表示的最大上升子序列，重点考虑如何去维护这个$dpdp$，以及如何去求得其长度$lenlen$。
• 初始化：$d{p}_0=ar{r}_0,len=1dp\_0\; =\; arr\_0,\; len\; =\; 1$
• 对于后续$i_{(1\le i\le n-1)}i\_\{(1\; \backslash leq\; i\; \backslash leq\; n-1)\}$,使用二分查找到$ar{r}_i>=d{p}_{j_{(0\le j\le n)}}arr\_i\; >=\; dp\_\{j\_\{(0\; \backslash leq\; j\; \backslash leq\; n)\}\}$,如果$ar{r}_i>d{p}_{current\mathrm{\_}end}arr\_i\; >\; dp\_\{current\backslash \_end\}$,直接在尾部插入$ar{r}_{i}arr\_i$，否则找到第一个$\ge ar{r}_i\backslash geq\; arr\_i$的位置将$ar{r}_{i}arr\_i$写入即可（可以理解为找到位置插入以后丢弃其之后的所有元素。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    vector<int> dp(n+1, INT_MAX);
    for(int i = 0; i < n; ++i){
        cin>> arr[i];
      	//在dp数组中找到>= arr[i]的位置，讲arr[i]写入忽略其后部分，因为其前部分一定和它构成上升子序列。
        dp[lower_bound(dp.begin(), dp.end(), arr[i])-dp.begin()] = arr[i];
    }
    int ans = 0;
    while(dp[ans] != INT_MAX) ans ++;
    cout<<ans;
    
    return 0;
}