最长上升子序列1

题目描述:
给一个长度为N的数列,求数列严格单调上升的子序列的长度是多少?
(1<=N<=1000)

DP思路:
f[i] 表示以a[i]结尾的最大上升子序列
所以我们就可以在(a[i]>a[j] 其中(j<i)的时候)通过f[i]来进行处理,即使用已经好的状态
最后我们只需要在f[i]里面找最大值就行

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 只有a[i]一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d\n", res);

    return 0;
}

代码来自:https://www.acwing.com/activity/content/code/content/58497/

最长上升子序列2 (N<=1e5)

思路：
使用二分优化

便于记忆的模板:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(void) {
    int n; cin >> n;
    vector<int>arr(n);
    for (int i = 0; i < n; ++i)cin >> arr[i];

    vector<int>stk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    cout << stk.size() << endl;
    return 0;
}

来自:https://www.acwing.com/solution/content/3783/