一本通-1259：【例9.3】求最长不下降序列（LIS）

【题目描述】 设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。

例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

【输入】 第一行为n,第二行为用空格隔开的n个整数。

【输出】 第一行为输出最大个数max(形式见样例)；

第二行为max个整数形成的不下降序列,答案可能不唯一，输出一种就可以了，本题进行特殊评测。

【输入样例】 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15

【输出样例】 max=8 7 9 16 18 19 21 22 63

---

#include <bits/stdc++.h>

using namespace std;

vector<int> num(205);
int n;
vector<int> d(205);
vector<int> pre(205, -1);


void print(int pos)
{
    if (pos == -1) return;
    else {
        print(pre[pos]);
        cout << num[pos] << ' ';
    }
}


void LIS()
{
    if (n == 1) {
        cout << "max=" << 1 << endl;
        cout << num[0] << endl;
        return;
    }

    d[0] = 1;
    for (int j = 1; j < n; ++j) {
        int maxLen = 0;
        int pos = -1;
        for (int i = 0; i < j; ++i) {
            if (num[i] <= num[j] && maxLen < d[i]) {
                maxLen = d[i];
                pos = i;
            }
        }
        d[j] = maxLen + 1;
        pre[j] = pos;
    }

    int position = -1;
    int res = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (d[i] > res) {
            res = d[i];
            position = i;
        }
    }

    cout << "max=" << res << endl;
    print(position);
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    return 0;
}

如果只是求LIS的长度，那么可以用二分查找加速，但是这里需要输出路径，所以需要使用动态规划的方法。用pre数组记录从哪个位置转移过来的，然后递归输出即可。

这道题也可以用二分加速的方法来做。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(205), d(205), pre(205, INT_MIN);

void print(int pos)
{
    if (pos == INT_MIN) return;

    print(pre[pos]);
    cout << seq[pos] << ' ';
}

void solve()
{
    d[1] = 0;
    d[0] = INT_MIN;
    int len = 1;
    for (int i = 1; i < n; ++i) {
        int target = seq[i];

        int left = 1, right = len + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (seq[d[mid]] <= target) left = mid + 1;
            else right = mid;
        }
        if (left == len + 1) {
            d[++len] = i;
            pre[i] = d[len - 1];
        }
        else {
            d[left] = i;
            pre[i] = d[left - 1];
        }
    }

    cout << "max=" << len << endl;
    print(d[len]);
    cout << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    return 0;
}

这里数组d[i] = pos表示最长不降子序列长度为i的时候，以原数组下标pos作为结尾，用pre[i]记录构成最长不降子序列的前一个元素的下标。最后递归输出路径即可。