最长非降子序列的O(n^2)解法

这次我们来讲解一个叫做“最长非下降子序列”的问题及他的O(n^2)解法。
首先我们来描述一下什么是“最长非下降子序列”。
给你一个长度为n的数组a，在数组a中顺序找到最多的元素（这些元素的顺序不能乱，但是可以不连续），使得这些找出的元素最多，同时要保证找出的元素的数列中前面的元素要小于等于后面的元素，则这些元素组成的一个新的数组就是这个数组的最长非下降子序列。
符合这样的一个要求的问题就是“最长非下降子序列”问题。其中最重要的就是前一个元素的值要小于等于后一个元素的值。
例如，给定一个数组a，其元素排列如下：

1 3 2 4 5

则

1 3 4 5

和

1 2 4 5

都是其最长非下降子序列。

如果将条件“小于等于”稍加改变，就会衍生出另外的一些问题，如：

• 小于：最长上升子序列
• 大于：最长下降子序列
• 大于等于：最长非下降子序列

不过我们可以很明显的看到，这些解决的都是同样的问题！所以我们在这个题目里面讲只重点讲解“最长非下降子序列”问题。

求最长非下降子序列有O(N*logN)的解法，不过我们在这篇随笔中先介绍O(n^2)的解法，以后有机会再介绍前面这种解法。

O(n^2)解法 —— 动态规划解法

我们可以发现，对于一个长度为n的数组a，我们同时开一个长度为n的数组f，其中f[i]表示以第i个元素结尾的最长上升子序列的长度，则状态转移方程可以表示为：

f[i]=max{f[j]+1}，其中0<=j<=i-1，并且a[j]<=a[i]

求解数组a的最长上升子序列的长度的代码如下：

#include <iostream>
using namespace std;
int a[10010], f[10010], n, s;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    s = 0;
    for (int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++)
        {
            if (a[j] <= a[i])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        if (f[i] > f[s])
        {
            s = i;
        }
    }
    cout << "max=" << f[s] << endl;
    return 0;
}

注意：代码中的变量s用于保存最长连续子序列的最后一个数的坐标，则其对应的f[s]即为最长连续子序列的长度。

输出一个最长非下降子序列

有的时候题目不仅要求最长非降子序列的长度，还要求这个最长非降子序列（即完整地输出这个最长非下降子序列），这个时候应该怎么办呢？
我们可以再开一个长度为n的数组pre，pre[i]表示第i个元素所在的最长非下降子序列中他的前一个元素的坐标，那么，如果我们可以编写如下的一个递归函数来顺序输出一个最大非下降子序列：

{
    if (i == -1)
        return;
    output(pre[i]);
    cout << a[i] << " ";
}

同时，我们在原来的程序当做稍作修改，增加了pre函数的初始化和pre的计算部分，改进的代码如下：

#include <iostream>
using namespace std;
int a[10010], f[10010], pre[10010], n, s;
void output(int i)
{
    if (i == -1)
        return;
    output(pre[i]);
    cout << a[i] << " ";
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    s = 0;
    for (int i = 0; i < n; i ++)
        pre[i] = -1;
    for (int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++)
        {
            if (a[j] <= a[i])
            {
                if (f[j] + 1 > f[i])
                {
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
            }
        }
        if (f[i] > f[s])
        {
            s = i;
        }
    }
    cout << "max=" << f[s] << endl;
    output(s);
    return 0;
}

该函数可以输出数组a的一个最长非下降子序列。

输出字典序最小的最长非下降子序列

按照我们之前的例子：

1 3 2 4 5

他有两个最长非下降子序列1 3 4 5和1 2 4 5，如果我们运行了上面的程序，当我们输入：

5
1 3 2 4 5

的时候，出来的结果是

max=4
1 3 4 5 

如果我们要求输出的最长非下降子序列是字典序最小的那个，则程序就出错了，原因在于我们没有对“字典序最小”这个条件进行处理。
那么怎么对“字典序最小”这个条件进行处理呢？我们就要稍微修改一下动态规划中求pre的状态转移方程了！
原来的状态转移方程式这样的：

            if (a[j] <= a[i])
            {
                if (f[j] + 1 > f[i])
                {
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
            }

要考虑字典序最小，我们在判断的时候不光要判断f[j] + 1 > f[i]的情况，还要判断f[j] + 1 == f[i]的情况，当f[j] + 1 == f[i]时，我们要判断一下a[j]和a[pre[i]]哪个小，如果a[j]要小，则我们必须要果断地将pre[i]的值改为j。
该部分改进的代码如下：

                if (f[j] + 1 > f[i])
                {
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
                if (f[j] + 1 == f[i])
                {
                    if (pre[i] != -1 && a[j] < a[pre[i]])
                        pre[i] = j;
                }

我们假设数组a的最长非下降子序列的长度为m，则通过上面的处理，我们已经保证了最长非下降子序列的前m-1个数是字典序最小的，那么怎么保证最后一个数是字典序最小的呢？
这个时候我们就要稍微处理一下s了（因为s是保存最后一个数的坐标的），我们原来的代码是这样的：

        if (f[i] > f[s])
        {
            s = i;
        }

但是光考虑f[i] > f[s]的情况在这里是不够的，我们还要考虑一下f[i] == f[s]的情况，在这种情况下我们要比较一个a[i]和a[s]的大小，如果a[i]<a[s]，则s应该被置为i，该部分改进的代码如下：

        if (f[i] > f[s])
        {
            s = i;
        }
        if (f[i] == f[s])
        {
            if (a[i] < a[s])
                s = i;
        }

所以，求一个数组a的字典序最小的最长非下降子序列的杨丽程序如下：

#include <iostream>
using namespace std;
int a[10010], f[10010], pre[10010], n, s;
void output(int i)
{
    if (i == -1)
        return;
    output(pre[i]);
    cout << a[i] << " ";
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    s = 0;
    for (int i = 0; i < n; i ++)
        pre[i] = -1;
    for (int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++)
        {
            if (a[j] <= a[i])
            {
                if (f[j] + 1 > f[i])
                {
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
                if (f[j] + 1 == f[i])
                {
                    if (pre[i] != -1 && a[j] < a[pre[i]])
                        pre[i] = j;
                }
            }
        }
        if (f[i] > f[s])
        {
            s = i;
        }
        if (f[i] == f[s])
        {
            if (a[i] < a[s])
                s = i;
        }
    }
    cout << "max=" << f[s] << endl;
    output(s);
    return 0;
}