0%

最长递增子序列

一、问题描述

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

二、解题思路

2.1、求解LIS的长度

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

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]的证明:

假设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具有“有序”性质,证明如下:

令在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的方案数

定义:

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]的证明:

假设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仍然具有“有序”性质,证明如下:

令在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;
您的支持将鼓励我继续分享!