最长上升子序列LIS

普通版本和二分版本：

原题链接：https://www.luogu.com.cn/problem/B3637

普通版本

AC代码：

using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N = 5e3 + 5;
int arr[N] = {0};
int dp[N] = {0};


int main()
{
	ios;
    int n, ans = 1;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        dp[i] = 1;
        for (int j = 0; j < i; j++){
            if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
            //如果arr[j] 小于 arr[i] 那么将dp[i]的值更新为dp[i]与dp[j]+1之间最大值
            ans = max(ans, dp[i]);
        }
    }

    cout << ans << '\n';
    return 0;
}

遍历arr中所有的元素，每个dp最后的值都为其最大值，再取最大的dp值作为ans

二分版本

AC代码：

using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N = 5e3 + 5;
int arr[N] = {0};
int dp[N] = {0};
int ed[N] = {0};

int main()
{
	ios;
    int n, len = 0, pos = 0;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        dp[i] = 1; //默认所有子序列长度为1
    }
    for (int i = 0; i < n; i++){
        pos = lower_bound(ed, ed+len, arr[i]) - ed; //寻找第一个不小于arr[i]的值的位置
        if (pos >= len){ //当该位置比目前最大子序列长度大时
            ed[len] = arr[i]; //目前长度尾最小值更新为arr[i]
            len++;
        }
        else{
            ed[pos] = arr[i]; //目前该位置最小值更新为arr[i]
        }
    }

    cout << len << '\n';
    return 0;
}

寻找每一个arr[i]值在目前最长子序列中的位置，若该位置大于等于目前最长子序列长度则说明该值可以成为新的末尾，否则对该位置的最小值进行更新，最后得到最长的上升子序列

二维递增版本

原题链接：*****************************************************************

牛客官方代码：

public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });

        vector<int> f = {envelopes[0][1]};
        for (int i = 1; i < n; ++i) {
            if (int num = envelopes[i][1]; num > f.back()) {
                f.push_back(num);
            }
            else {
                auto it = lower_bound(f.begin(), f.end(), num);
                *it = num;
            }
        }
        return f.size();
    }
};

在前一道题中我们的判断条件可以是等于，但是本题中因为需要将套娃进行嵌套，所以两个套娃之间必须严格大于或小于对方。若envelopes[i][1] 比子序列f末尾的值大则可以将子序列f嵌套在其中，否则寻找其在子序列中可嵌套的位置并对该位置的最小值进行更新。