最长递增子序列

一、问题描述

最长递增子序列：英文名为“Longest Increasing Subsequence”，简称“LIS”，就是在序列中找到最长递增子序列，一般常见的有“求解LIS的长度，求解LIS的方案数，打印1个LIS方案”3个细分问题。

二、解题思路

2.1、求解LIS的长度

动态规划解决。
以sequence指代原序列。
定义：

1	dp[len]=sequence[p]，表示最长递增子序列长度为len时，所有len长度最长递增子序列方案中所有第len个元素构成的集合中具有最小值的元素为sequence[p]

构造：

int len = 1;
dp[len] = sequence[0];

for (int index = 1; index < length; index++) {
    // 更新dp，看是否值需要更新成sequence[index]

    // 具体策略是：找到最大maxlen，使得dp[maxlen]<sequence[index]，则dp[maxlen+1]=sequence[index]
    int left = 1, right = len, mid;
    while (left <= right) {
        mid = (left + right) >> 1;

        if (dp[mid] < sequence[index]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    dp[left] = sequence[index];

    if (left > len)
        len = left;
}

只需更新dp[maxlen+1]为sequence[index]的证明：

1
2
3

假设n>0，则：
1、dp[maxlen+1+n]不可能更新成sequence[index]，否则dp[maxlen+n]<sequence[index]，跟“找到最大maxlen”矛盾
2、令“dp[maxlen+1]=sequence[index]”对应的最长递增子序列中第“maxlen+1-n”个元素为sequence[m]，则有sequence[m]<sequence[index]，又根据dp定义，有dp[maxlen+1-n]<=sequence[m]，则最终有dp[maxlen+1-n]<sequence[index]，因此dp[maxlen+1-n]不可能更新成sequence[index]

根据上述构造过程，可知算法时间复杂度为O(n*n)。
dp具有“有序”性质，证明如下：

1	令在dp[len]这个最长递增子序列中第“len-n”个元素为sequence[m]，则有sequence[m]<dp[len]，又根据dp定义，有dp[len-n]<=sequence[m]，则最终有dp[len-n]<dp[len]

根据dp的“有序”性质，上述构造过程中的“找到最大maxlen”步骤显而易见可采用“二分查找法”策略进行优化，从而将算法的时间复杂度优化为O(n*logn)。

2.2、求解LIS的方案数

定义：

1
2

tail[p]=len，表示以sequence[p]为最长递增子序列末尾元素时，该最长递增子序列的长度为len。tail在求解LIS长度时顺带构造
number[p]=num，表示以sequence[p]为最长递增子序列末尾元素时（此时该最长递增子序列的长度为tail[p]），方案数为num

构造：

for (int index = 0; index < length; index++) {
    int num = 0;
    for (int preIndex = 0; preIndex < index; preIndex++) {
        if (sequence[preIndex] < sequence[index]) {
            if (tail[preIndex] + 1 == tail[index]) {
                num += number[preIndex];
            }
        } else if (sequence[preIndex] == sequence[index]) {
            if (tail[preIndex] == tail[index]) {
                //去掉重复方案，比如“3 4 3 4 5”只有1种方案，而不是3种
                number[preIndex] = 0;
            }
        }
    }

    if (num == 0) {
        num = 1;
    }

    number[index] = num;
}

去掉重复方案逻辑正确性的证明：

经过逻辑推理可知，重复方案存在且只存在于同时满足“sequence[preIndex] == sequence[index]”和“tail[preIndex] == tail[index]”两个条件的情形中，因此只需对该种情形进行方案去重处理即可

2.3、打印1个LIS方案

获取最简单的一个LIS方案方法如下：

int[] oneSolution = new int[lenOfLIS];
for (int index = lenOfLIS; index >= 1; index--) {
    oneSolution[index - 1] = dp[index];
}

return oneSolution;

dp的“有序”性质确保了上述方法的正确性。

三、变种

变种有：

最长不递减子序列，英文名为“Longest Non-Decreasing Subsequence”，简称“LNDS”
最长递减子序列，英文名为“Longest Decreasing Subsequence”，简称“LDS”
最长不递增子序列，英文名为“Longest Non-Increasing Subsequence”，简称“LNIS”

接下来再探讨LNDS问题解题思路。而LDS和LNIS问题解题思路则分别可由LIS和LNDS问题解题思路简单推得。

3.1、LNDS

3.1.1、求解LNDS的长度

这里构造中须将dp[maxlen]<sequence[index]改成dp[maxlen]<=sequence[index]：

int len = 1;
dp[len] = sequence[0];

for (int index = 1; index < length; index++) {
    // 更新dp，看是否值需要更新成sequence[index]

    // 具体策略是：找到最大maxlen，使得dp[maxlen]<=sequence[index]，则dp[maxlen+1]=sequence[index]
    int left = 1, right = len, mid;
    while (left <= right) {
        mid = (left + right) >> 1;

        if (dp[mid] <= sequence[index]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    dp[left] = sequence[index];

    if (left > len)
        len = left;
}

这里只需更新dp[maxlen+1]为sequence[index]的证明：

1
2
3

假设n>0，则：
1、dp[maxlen+1+n]不可能更新成sequence[index]，否则dp[maxlen+n]<=sequence[index]，跟“找到最大maxlen”矛盾
2、令“dp[maxlen+1]=sequence[index]”对应的最长不递减子序列中第“maxlen+1-n”个元素为sequence[m]，则有sequence[m]<=sequence[index]，又根据dp定义，有dp[maxlen+1-n]<=sequence[m]，则最终有dp[maxlen+1-n]<=sequence[index]，因此dp[maxlen+1-n]或者不可能更新成sequence[index]（当dp[maxlen+1-n]<sequence[index]），或者没必要更新成sequence[index]（当dp[maxlen+1-n]=sequence[index]）

这里dp仍然具有“有序”性质，证明如下：

1	令在dp[len]这个最长不递减子序列中第“len-n”个元素为sequence[m]，则有sequence[m]<=dp[len]，又根据dp定义，有dp[len-n]<=sequence[m]，则最终有dp[len-n]<=dp[len]

3.1.2、求解LNDS的方案数

这里构造中不再需要考虑“方案重复”情形：

for (int index = 0; index < length; index++) {
    int num = 0;
    for (int preIndex = 0; preIndex < index; preIndex++) {
        if (sequence[preIndex] <= sequence[index]) {
            if (tail[preIndex] + 1 == tail[index]) {
                num += number[preIndex];
            }
        }

        if (num == 0) {
            num = 1;
        }

        number[index] = num;
    }
}

3.1.3、打印1个LNDS方案

跟LIS一致。

四、完整的源代码

完整的源代码见LIS。

五、另外一种解题思路

5.1、求解LIS的长度

直接根据tail数组求解。
具体代码如下所示：

public int lengthOfLIS() {
    tail = new int[length];

    int totalMax = -1;

    for (int indexA = 0; indexA < length; indexA++) {
        int maxtmp = 1;

        for (int indexB = 0; indexB < indexA; indexB++) {
            if (sequence[indexB] < sequence[indexA]) {
                if (tail[indexB] + 1 > maxtmp) {
                    maxtmp = tail[indexB] + 1;
                }
            }
        }

        tail[indexA] = maxtmp;

        if (maxtmp > totalMax) {
            totalMax = maxtmp;
        }
    }

    lenOfLIS = totalMax;

    return lenOfLIS;
}

上述算法的时间复杂度为O(n*n)。

5.2、求解LIS的方案数

跟“2.2、求解LIS的方案数”一致。

5.3、打印1个LIS方案

具体代码如下：

int[] oneSolution = new int[lenOfLIS];

int len = lenOfLIS;
for (int index = length - 1; index >= 0 && len >= 1; index--) {
    if (tail[index] == len) {
        oneSolution[len - 1] = sequence[index];
        len--;
    }
}

return oneSolution;