动态规划之最长递增子序列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAXN 100005

// a:存储输入的数据的数组
// l:以位i结尾且包含位i的LIS
// p:以位i结尾且包含位i的LIS的倒数第二位的坐标

ll a[MAXN] = {0}, l[MAXN] = {0}, p[MAXN] = {0};
int n;


bool cmp(const ll &a,const ll &b)
{
    return a>b;
}

ll dp()
{
    p[0] = -1;

    //当前正在找以第i位为结尾的LIS
    for (int i = 1; i <= n; ++i)
    {
        int k = 0;

        //找到之前的满足条件的LIS
        for (int j = 0; j < i; ++j)
        {
            if (a[i] > a[j] && l[j] > l[k])
                k = j;
        }

        p[i] = k;
        l[i] = l[k] + 1;
    }

    sort(l+1,l+n+1,cmp);

    return l[1];
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    cout<<dp()<<endl;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define MAXN 100005

int n;
int a[MAXN] = {0};
int L[MAXN] = {0};
int length = 0;

ll dp()
{
    length = 1;
    L[0] = a[0];

    /*
    *   主要思路：
    *       用L[i]来存储一个递增序列，每一位表示长度为i+1的递增子列的末尾最小值
    * 
    *       不断考虑原数列的每一位，若其小于LIS的最大元素，则将其加到LIS末尾
    *       否则将LIS中第一个大于等于它的元素替换成它。（也就是相应长度的递增子列的末尾元素最小值）
    *           我们希望借此能更新掉原来最长的子列的最大元素，这样才能为递增子列的延长提供便利。
    * 
    */

    for (int i = 1; i < n; ++i)
    {
        if (L[length - 1] < a[i])
            L[length++] = a[i];
        else
            *lower_bound(L, L + length, a[i]) = a[i];
    }

    return length;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    cout << dp() << endl;
}