一、题目及概念

1、题目描述

2、子序列

  先引入一段来自百度百科的介绍：子序列简称子列.指序列的一部分项按原有次序排列而得的序列.设｛an｝∞n=1是序列，k1<k2<…<kn<…是一列正整数，则称序列｛akn｝∞n=1为｛an｝∞n=1的子序列或部分列.
  但显然，这样的描述对理解并不是特别的友好，所以这里进行简单一些的描述。子序列简单来讲，就是从给定的序列中，挑出一些元素，在保持原先先后顺序的情况下组合。
  比如给定序列A=[1, 2, 3, 4, 5],序列A1=[1, 3, 5],A2=[1, 2, 3]是A的子序列，但序列B=[1, 3, 2]不是，因为它打破了元素原来的先后顺序，在原来的序列A中，2是在3前面的；而序列B中3在2前面了。

3、增长（或上升）子序列

  其实从字面上也很好理解，就是该子序列一定是升序的，如序列A=[4, 5, 1, 2, 3]，序列A1=[1, 2, 3]是增长子序列，而序列A2=[4, 1, 3]就不是，因为4>1了，破坏了增长的结构。

4、最长增长子序列

  这个就更容易理解了，还是如上面的序列A=[4, 5, 1, 2, 3]，序列A1=[1, 2, 3]是最长增长子序列，而序列A2=[4, 5]就不是了，很明显，A1和A2都是增长子序列，但A1的长度要大于A2。

二、分析并解决题目

1、寻求解决问题的方法

  大家都知道，像这种类型的题目，使用枚举法肯定是不行的，他的时间复杂度会是指数级的。比如使用最简单的枚举方法，所有可能的序列共有2^n个，即使不考虑其他操作所需的开销，它的时间复杂度也是指数级的，这意味着几乎随便找另一个算法都会比这个强。
  这里我们使用动态规划的思想来解决这个问题。动态规划简单来说就是将一个问题划分成一个个子问题，通过寻求子问题的最优解来解决这个问题。这里要是有了解过分治法的同学可能会有疑问，分治法不也是划分子问题求解吗，这和动态规划有什么区别吗。实际上，当子问题不是相互独立的时候，使用分治法的时候会产生重复的子问题，而解决重复子问题会造成额外的开销。而动态规划会额外开辟一块空间来记录每个子问题的解，当要用到一个子问题的解的时候，先看这个问题是不是已经被计算过一次了，如果没有的话计算出结果并存起来等待下次的使用，否则直接拿来用就好。
  另外分治法不需要考虑子问题的复用，所以直接利用递归，从上到下划分子问题，然后从边界回溯解决子问题，可以说是从上到下的结构；但动态规划涉及到子问题的记录，所以要从子问题开始计算，然后将子问题进行归并，所以一般按照之前设定的规则（状态转换方程）从下向上进行求解。
  这里只是解决具体的问题，如果你之前没有了解过分治法或动态规划，可以去学习一下，对以后的学习会有好处。

2、构建动态规划的模型

（1）分析优化解的结构

  我们首先划分子问题。假设有一个序列[a, b, c, d, e, f, g]，我们已经知道序列[a, b, c, d, e, f]的最长增长子序列（以后称其为最优解），那我们如何获取[a, b, c, d, e, f, g]的最优解呢？我们只需知道序列[a, b, c, d, e, f]中最大的元素m，将其与g比较，如果m<=g，就将g放在[a, b, c, d, e, f]的最优解的后面，否则就不加；相似的我们要获取[a, b, c, d, e, f]的最优解，就要知道[a, b, c, d, e]的最优解以及[a, b, c, d, e]的最优解中最大的元素……依次拆分，便可得到[a, b, c, d, e, f, g]的最优解。
  所以该问题的优化子结构便是子序列的最优解以及子序列最优解中元素的最大值。

（2）构造状态转换方程

  优先，我们要决定储存子问题解的数据结构，这里我们用a[]来表示要求解的序列（即输入），二维数组s[i][j]=m来储存子问题的最优解。
  其中i（即行）代表的是最优解的长度；j（即列）代表的是a[j]结尾的子序列；m是最优解中最大的元素。
  用语言描述s[i][j]=m就是：以a[j]结尾的长度为i的最长增长子序列中最大的元素是m。
  根据之前分析的优化解的结构，我们可以得到状态方程：

  以及边界条件：

（3）优化解的构建过程

  首先，我们给出一个序列a[5]=[4, 5, 1, 2, 3]，之后的操作都是围绕它来进行。
  构造s[i][j]：

  j表示a[]的下标，a[j]表示对应的元素的值；i表示最长增长子序列的长度。
  在计算子问题的解之前首先我们要先知道，由于一个序列的最长增长子序列不会大于它的长度，所以数组有一部分区域（右下向对角线（不包括对角线）的左下方区域）是用不到的：

  让我们开始吧！
  首先按照状态转换方程从最左上角开始，因为以某个元素为结尾的子序列长度只能为1，所以第一行的值是a[j]:

  然后从第二行与对角线的交点开始填充第二行的数据，举s[2][2]的例子，因为

即a[2]>s[1][1]，即5>4，所以s[2][2]=5，然后依次向左按照此规律填充：

  第三行：
  第四行：
  第五行：
  到此，s[i][j]的填充即子问题的求解就算结束了，此时我们发现，深度最大的是以a[5]为结尾的最长增长子序列，即我们要求的解，为3。
  因为a[5]为结尾的最长增长子序列便是我们输入序列的最长增长子序列，所以最右列不为∞的深度即我们要求的答案。

3、存储结构的优化

  回顾一下状态转换方程以及上面的求解过程，发现每求一个子问题的解都要遍历一遍左上那一行的元素并与该列对应的元素比较大小，只要该列对应的元素比其中一个大就可以，那我们是不是可以只记录每一行的最小值呢，代表长度为i的所有增长子序列中最大元素中的最小值。
  让我们来尝试一下。

（1）优化存储结构

  我们仅需一个可变长度的一维数组，可用指针来表示，这里为了方便理解，我们仅用一个一维数组s[i]来表示长度为i的所有增长子序列中最大元素中的最小值 以及 top代表可变长度数组的尾部下标。

（2）思路

  最开始top是-1，代表可变长度的数组最开始是0。我们从左到右遍历a[]，当a[i]大于等于s[top]的时候，s[]长度加一，即top+1，然后将使s[top]=a[i]；当a[i]小于s[top]的时候，向左遍历s[]，找到s[m]与s[m+1]，使s[m]<=a[i]<s[m+1]，然后将s[m+1]替换成a[i]，即s[m+1]=a[i]。
  这样做的原因是为了简化找到最大增长子序列长度的过程，注重长度，淡化子序列的顺序性。

（3）状态转换方程

（4）举例

  对于序列a[5]=[4, 5, 1, 2, 3]:

  从左到右开始遍历，当i=0：

  继续遍历，当i=1：

  继续遍历，当i=2：

  继续遍历，当i=3：

  继续遍历，当i=4：

  遍历结束后发现s[]最终的长度为3，所以最长增长子序列的长度是3.

4、记录最长增长子序列

  至此，我们便解决了求最长增长子序列的长度的问题，但题目中还要求输出该最长增长子序列，我们先只输出其中一个最长增长子序列（因为可能有多个长度相同的最长增长子序列）。

（1）思路

  设定p[j]，记录在优化解中a[j]的上一个元素m，而m在s[i]中的体现就是：当s[x]=a[j]时，p[j]=s[x-1]。是不是有点懵，没关系，下面我们来举一个例子，相信大家看完就明白了。

（2）举例

  这里我们还是使用a[5]=[4, 5, 1, 2, 3]来举例。
  初始化存储结构：
  下面开始遍历，当i=0时：

  i=1：

  i=2：

  i=3：
  i=4：
  到此优化解的信息就填充完毕了，以下是结果图：

  得到最长增长子序列的长度是s.length=3，而具体的最长增长子序列通过s[]记录的最后一个元素查p[]获得。如下：
  先找到最长增长子序列的最有后一个元素的前一个元素：

  发现是2，那就再找2的前一个元素：

  再找1的前一个元素：

  发现1之前没有元素了，所以最长增长子序列便是123：

  注意的是，这里s[]和seq一样是巧合，大家可以用[2, 1, 3, 4]试一下。

5、优化后的时间空间复杂度分析

  由于只用到数组a[]、s[]、p[]，所以空间复杂度是O(n)；
  时间复杂度暂定O(nlogn)。

三、算法实现

  为了简化判断量，这里我们对上面的存储结构进行小小的修改：
1、在a[]、s[]、p[]三个数组前都加一个0（为了减少判断以及让下标从1开始）
2、使s[]和p[]中存对应元素的下标而不是对应的值（因为值是可能重复的，为了容易理解，上面在s[]和p[]中存的都是具体的值，[4, 5, 1, 2, 3]也没有重复的元素）

1、c语言实现

#include<stdio.h>

#define LENGTH 6  // 序列长度

#define START 0

//int t[LENGTH] = {4, 5, 1, 2, 3};
int t[LENGTH] = {2, 3, 1, 4, 5, 4};  // 要求解问题的序列，可以换成自己输入

int max[LENGTH + 1];  // 记录所有长度的所有增长子序列中最大元素中的最小值，即上面讲的s[]

int pre[LENGTH + 1];  // 记录每个元素前一个元素的数组，即上面讲的p[]

int top = 0;  // max[]的尾端下标

int a[LENGTH + 1];  // t[]最开始填一个0

int main()
{
    init(pre);  // 初始化记录前一个元素的数组，最前面加个0
    init(max);  // 初始化记录每个长度的最优解最大值的数组，最前面加个0
    initArr(a);  // 初始化要求解问题的序列
    // 构建max[]以及pre[]
    for(int i = 1; i < LENGTH + 1; i++){
        if(a[i] >= a[max[top]]){
            pre[i] = max[top];
            top++;
            max[top] = i;
        } else {
            for(int j = top - 1; j >= 0; j--){
                if(a[i] >= a[max[j]]){
                    pre[i] = max[j];
                    max[j + 1] = i;
                    break;
                }
            }
        }
    }
    printf("max length: %d\n", top);
    printf("seq: ");
    printSeq(max[top]);  // 打印出求得的序列
    return 0;
}

// 初始化 max[] 和 pre[]，在最前面加个0
void init(int *a){
    for(int i = 0; i < LENGTH + 1; i++){
        *(a + i) = START;
    }
}

// 初始化输入数组，在最前面加个0
void initArr(int *a){
    *a = START;
    for(int i = 1; i < LENGTH + 1; i++){
        *(a + i) = t[i - 1];
    }
    return a;
}

// 递归打印最优解元素
void printSeq(int i){
    if(pre[i] == START){
        printf("%d ", a[i]);
        return;
    }
    printSeq(pre[i]);
    printf("%d ", a[i]);
}

  序列[2, 3, 1, 4, 5, 4]运行结果如下：

四、后记

  到此，算法就算是完成了，但是这个方法只能输出其中一个最长增长子序列，当有多个最长增长子序列时只输出一个，有的时候会不符合要求。而且我个人感觉，求出所有最长增长子序列的算法就算不上是动态规划了，因为动态规划是通过子问题的最优解来求父问题的最优解，而想要求出所有最长增长子序列，就意味着要同时维护多个可能为最长增长子序列的序列，有了这种不确定性，我便觉得这不是动态规划了。当然，思路也非常简单，就是在记录前一个元素的数组（在上面的算法中是p[]）中，每个元素维护一个链表，回溯的时候树状回溯便可以了。（当然，上面的算法应该是不能用此方法，要想求出所有最长增长子序列，就得换一个思路，不过这里就不讲了，其实就是网上绝大多数的思路）
  希望大家能有所收获，有问题的话可以评论。