这是第二篇题解呢

点我传送

题目大意

【题目描述】

一个数的序列bi，当b1<b2<...<bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)，这里1≤i1<i2<...<iK≤N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

【输入】

输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

【输出】

最长上升子序列的长度。

思考

我们的目标是求出最长的不连续的上升数列,那么我们开一个数组f[i],存以i结尾的数列长度;

那么,对于每一个数i,我们从她前面找一个比她小的数字j,判断和她连接后长度是否比当前长度长,是的话则替换fi的值.

方程式大致如下

fi = max(fj+1,fi) | fi > fj

code

#include <iostream>
#include <algorithm>
#define maxn 100005
using namespace std;

int n, a[maxn] = {};

int f[maxn] = {};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
        {
            if (a[i] > a[j])
            {
                f[i] = max(f[j] + 1, f[i]);
            }
        }
    cout << *std::max_element(f + 1, f + n + 1) << endl;
    return 0;
}

优化 update 2019.10.05

LIS其实可以优化到O(nlogn)

有这么一个串：

3 1 5 2 7 6

我们考虑开一个数组记录最长子串而不是记录以i结尾的串长度。

for (register int i = 1; i <= n; i++)
{
    if(....)
        .....
    else
        .....
}

我们每添加一个数，比较他与我们记录最长子串的数组最后一个数大还是小，如果大就直接加入数组末尾。

for (register int i = 1; i <= n; i++)
{
    if(a[i] > s[len])
        s[++len] = a[i];
    else
        .....
}

不然我们就二分找一个比a[i]大的最小元素，然后替换，如果它不会更新答案，那么它也就不会更新到末尾，也就不会影响答案。还有我们求的是长度，和里面的元素无关。

int lower_bound(int x)
{
    int l = 1, r = len;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (s[mid] < x)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

for (register int i = 1; i <= n; i++)
{
    if(a[i] > s[len])
        s[++len] = a[i];
    else
        s[lower_bound(a[i])] = a[i];
}

cout << len;