最长递增子序列长度的两种公式解法

shaowu459

最长递增子序列（longest increasing subsequence）问题是指在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的，并且可能有多个长度相同的最长递增子序列。

以[1,3,6,2,4,5]这个序列来说，最长递增子序列长度是4，长度是4的递增子序列有两个，分别是[1,3,4,5]和[1,2,4,5]。

最长递增子序列问题是编程领域一个经典问题，其他问题有时也会转化为求最长递增子序列问题。本帖介绍使用REDUCE函数求最长递增子序列长度的两种公式写法（公式并非最短，主要用来说明解题思路），其中一种方法还可以用于解决山脉数组问题。

shaowu459

题目数据描述如下：
下图中每行11个正整数是需要求最长递增子序列的数组，需要返回每行数组中最长的递增子序列长度。如果数组是单调不增序列（如第9行数组），要求返回1，也即单个数字可视为长度为一的递增子序列。图中黄色标示的是每行最长递增子序列的一种情况，供参考。

shaowu459

我们仍以[1,3,6,2,4,5]这个数字为例来分析一下如何获得最长的递增子序列。因为要求的子序列是递增的，所以我们可以考虑遍历从头开始遍历每个元素，然后观察挑出能保证子序列递增并尽可能长的数组元素的规律。挑出的数字可以存储进一个结果数组，这个数组的元素是单调递增的，在遍历原数组时，每个元素和这个结果数组的元素进行比较，可以直接追加到结果数组或根据某些规律替换数组中的元素，类似模拟单调递增栈的用法。

遍历第一个元素1时，因为此时结果数组为空，所以1可以直接进入结果数组。


遍历第二个元素3时，因为3比结果数组里的1要大，是递增的趋势，因此3可以直接进入结果数组顶端，结果数组一直保持从下到上是递增的，最大值永远在数组顶端。


遍历第三个元素6时，因为6比结果数组中的顶端元素3要大，是递增的趋势，因此6可以直接进入结果数组顶端，结果数组一直保持从下到上是递增的，最大值永远在数组顶端。


当遍历第四个元素2时，2小于结果数组顶端的6，因为结果数组要是单调递增的，所以2不能堆积在结果数组顶端，但是这个2是不是直接舍弃呢？

来看一个简单的例子，在求[1,4,2,3]这个数组的最长递增子序列时，前两个元素直接进入结果数组[1,4]，此时遍历到第三个元素2，那么用2替换结果数组顶端的4，仍然能保证结果数组是递增的，并且还使这个结果数组尽量小了，也就是增长的幅度尽量降低，这样后面再有比2大但是比4小的元素也就可以进入结果数组，序列长度就能尽可能长了。用2替换4后结果数组是[1,2]，遍历最后一个元素3时，因为3大于结果数组顶端的2，因此也可以进入结果数组，最后的结果数组就是[1,2,3]了，如果不用2替换4，那么结果数组就只能是[1,4]。

通过上面的分析，我们可以用2替换结果数组中的3，这个数字是结果数组中大于等于2的所有数字中最小的那个。不能用2去替换1，因为2替换1后整个结果数组上升的幅度或者说速度就增加了，这不是我们需要的效果。替换完成后，结果数组就变成了[1,2,6]，如下图所示：



需要注意的是：这种替换能保证结果数组的元素个数不变，但是这个结果数组并不一定是最长递增的那个子序列。也就是说，最终结果数组的长度是最大的，但是结果数组可能不是最长递增子序列中的任何一种情况。

同理，遍历下一个元素4时，因为4小于结果数组顶端的6，并且大于结果数组中的其他元素，因此用4替换6，让结果数组增长的尽可能慢，以保证后面能有尽可能多的元素添加到结果数组里来。


最后，遍历5时，因为5大于结果数组顶端的4，直接加入结果数组即可。


观察最终的结果数组是4个元素，因此原数组的最大递增子序列最大长度就是4。

shaowu459

使用REDUCE函数可以用于追加或替换数组元素的功能，因此可以使用REDUCE函数来完成维护和更新结果数组的功能。先放上公式，然后再分步介绍公式运算过程。

1. =ROWS(REDUCE(,A2:K2,LAMBDA(x,y,IF(y>@x,VSTACK(y,x),IF(x=MIN(IF(x>=y,x)),y,x)))))

复制代码

shaowu459

接下来仍以[1,3,6,2,4,5]为例，分步介绍REDUCE函数运算过程。

遍历第一个元素时，由于REDUCE函数省略了第一参数，因此1直接进入x。


遍历到3时，将3追加到x顶端：


遍历到6时，将6追加到x顶端：



遍历到2时，用2替换x中大于等于2的最小值3：


遍历到4时，用4替换x中大于等于4的最小值6：


遍历到5时，将5追加到x顶端：


最后，使用ROWS函数统计REDUCE函数返回的结果数组行数即可获得原数组最长递增子序列的长度。

shaowu459

公式简要说明如下：

=ROWS(      统计结果数组的行数
    REDUCE(
        ,   省略一参，使数组第一个值直接进入x
        A2:K2,
        LAMBDA(x, y,
            IF(
                y > @x,        如果y大于x顶端的值（也就是比x中的任意元素都要大，因为x是单调递增的）
                VSTACK(y, x),  则将y追加到x顶端
                IF(x = MIN(IF(x >= y, x)), y, x)   如果y不大于x顶端的值，则用y替换x中大于等于y的值中最小的那个。
            )
        )
    )
)


因为x中维护的是单调递增数组，因此数组中的元素无重复，公式中y值替换部分也可以修改为以下写法：


=ROWS(
    REDUCE(
        ,
        A2:K2,
        LAMBDA(x, y,
            IF(
                y > @x,
                VSTACK(y, x),
                IF(x = -LOOKUP(-y, -x), y, x)    使用LOOKUP获取x中大于等于y的最小值
            )
        )
    )
)

shaowu459

接下来介绍第二种公式写法，仍然使用REDUCE函数。在这个公式中，我们要维护一个多行两列的数组，每行的数组第一个元素为遍历的原数组中的数值，第二个元素为截止到该值为止以该值为最大值的最长递增子序列的长度。为方便运算，给x设定一个初始值为{0,0}：



参考公式写法如下，后面将分步说明公式运算过程。

1. =MAX(DROP(REDUCE({0,0},A2:K2,LAMBDA(x,y,VSTACK(x,HSTACK(y,1+MAX(FILTER(DROP(x,,1),TAKE(x,,1)<y)))))),,1))

复制代码

shaowu459

遍历数字1时，筛选x的第二列，条件是x的第一列数字小于1。因为只有初始值0小于1，因此获取0对应的第二列值0再加上1，作为到数字1为止，以1为最大值的最长递增子序列长度。返回的结果{1,1}代表的是{遍历的数字，到数字1为止以1为最大值的最长递增子序列长度}。


遍历数字3时，同样筛选x的第二列，条件是x的第一列数字小于3。此时x第一列中的0和1都小于3，因此筛选出第二列的{0;1}，取最大值为1。也就意味着：在3之前，有小于3的数字最大递增子序列长度是1，因此到3，这个序列长度可以再加上1。因此，到3为止，以3为最大值的最长递增子序列长度就是2（这个子序列是[1,3]）。



遍历数字6时，x第一列中所有数字都小于6，第二列的最大值为2（数字3对应的最大递增子序列长度），因此截止到数字6的最大递增子序列长度就是2+1，也即6可以增加之前的最长子序列[1,3]的后面，使子序列长度增加1，变成[1,3,6]。因此，到6为止，最长的递增子序列长度就是3。所以在x里增加{6,3}这一行。


遍历数字2时，x第一列中小于2的值只有0和1，对应的最长递增子序列长度最大值是1，因此到这个2为止以2为最大值的最长递增子序列长度是1+1=2，也即子序列[1,2]的长度。



遍历数字4时，x第一列小于4的数字有多个，对应的最长递增子序列长度最大值为2（数字3和数字2对应的），因此到这个4为止以4为最大值的最长递增子序列长度是2+1=3，也即子序列[1,3,4]或[1,2,4]的长度。



遍历数字5时，x第一列小于5的数字有多个，对应的最长递增子序列长度最大值为3（数字4对应的），因此到这个5为止以5为最大值的最长递增子序列长度是3+1=4，也即子序列[1,3,4,5]或[1,2,4,5]的长度。


最后，再提取结果数组最后一列的最大值即可。

shaowu459

公式简要说明如下：

=MAX(         取REDUCE函数返回结果最后一列的最大值
    DROP(     去掉第一列，保留REDUCE函数返回结果的最后一列
        REDUCE(
            {0, 0},    设定初始值
            A2:K2,
            LAMBDA(x, y,
                VSTACK(
                    x,
                    HSTACK(
                        y,     横向堆叠当前遍历的原数组元素
                        1 +    在小于当前值的元素最大递增序列基础上+1
                            MAX(
                                FILTER(     筛选
                                    DROP(x, , 1),    筛选x第二列，存储的是到对应数字的最大递增序列长度
                                    TAKE(x, , 1) < y  筛选条件为x第一列小于当前遍历值
                                )
                            )
                    )
                )
            )
        ),
        ,
        1
    )
)

shaowu459

本帖说明结束。最后一个公式第一次使用是在解决山脉数组问题中，关于山脉数组的题目和公式请在我个人前面链接里的〖X档案大揭秘〗帖子中查找一下。