Question

Longest Increasing Subsequence（LIS）

中文可以译做“最长递增子序列”。先来介绍 subsequence 这个字吧！subsequence 是 sub + sequence，sub 有著“次要”的意思，而 sequence 是指数学之中的“数列”、“序列”。

1 3 5 2 9

像是 1 3 5 2 9 就是一个由五个数字组成的 sequence。至于 subsequence，是指从一个 sequence 之中，依照由左到右的顺序，挑几个数字出来，就是 subsequence。

3 9

例如 3 9 就是 1 3 5 2 9 的其中一个 subsequence。

1 5 2 9

例如 1 5 2 9 也是 1 3 5 2 9 的其中一个 subsequence。至于空集合、原来的 sequence，也都是 1 3 5 2 9 的 subsequence！

接下来介绍 increasing 这个字。increasing 是指数学中的“严格递增”，就是数字不断增加。例如 1 3 5 2 9 就不是一个递增的 sequence──因为在 2 的地方，这个 sequence 是在减少而非增加。至于 3 9 才是一个递增的 sequence。

每一个 sequence 都有长度。1 3 5 2 9 的长度就是五，因为它由五个数字组成；3 9 的长度就是二，因为它由两个数字组成。LIS 是指一个 sequence 当中，它拥有最长的长度、且严格递增的那些 subsequence（不一定只有一个）。1 3 5 2 9 的 LIS 是 1 3 5 9 这个 subsequence。

通常 LIS 的问题，只会要我们求出 sequence 的其中一个 LIS 即可。

要解决 LIS 的问题，主要有两种演算法，一种是 O(N^2) 的，一种是 O(NlogN)。先讲简单易懂的 O(N^2) 吧！

Longest Increasing Subsequence: Dynamic Programming

Recurrence

length(n) =  max  { length(i) + 1 : if s[i] < s[n] }
           0≤i≤n-1

n：第 0 项到第 n 项的 LIS。
length(n)：第 0 项到第 n 项的 LIS 长度。
s[n]：第 n 项数值。

计算 Longest Increasing Subsequence 的长度

这裡提供两支程式码，效果一样！第一支程式码是看 s[i]后面能接上哪些数字，第二支程式码是看 s[i]能接在哪些数字后面。

Longest Increasing Subsequence: Robinson-Schensted-Knuth Algorithm

演算法

採取 Greedy 策略，以 Binary Search 加速，达到 O(NlogL)，N 是给定序列的长度，L 是 LIS 的长度。

计算 Longest Increasing Subsequence 的长度

很多演算法的书上都有提到此演算法，所以就不赘述了。用 C++ STL 写成的程式码短短的很可爱：

找出一个 Longest Increasing Subsequence

很多演算法的书上都只说到如何去计算出 LIS 的长度，而没有说要怎麽列出 LIS。这裡介绍列出 LIS 的方法。

首先找到每个数字在 LIS 当中的合适位置 position[]，接下来就可以从 position[]裡面找到真正的 LIS。从尾巴开始往回找，先找到的就是正确的。因为 LIS 长度为 4，所以就先找位置为 4 的。

最后得到 LIS 为-7 2 3 8。

LIS 可能不止一个。上述方法会得到最后出现的 LIS。若是要得到最先出现的 LIS，该怎麽办呢？最简单的方式是：原本序列由右至左的做 Longest Decreasing Subsequence 就行了。

非严格递增的 Longest Increasing Subsequence

请先看看这个例子。

这个时候就不能用 8 来代替 8，而要用 8 去代替比 8 稍大的数字。如果找不到比 8 稍大的数字，则直接将数字加在后面。上面的例子修改过后，就变成这样。

找出所有的 Longest Increasing Subsequence

如果题目修改成：请列出所有的 LIS。这样的话，我也不知道怎麽解决了。可能要写个递迴找出所有答案吧？

演算法讨论

宏观来看，这个演算法找出了所有的 increasing subsequence，并依照特定顺序排列。然后按顺序记下几个优良的 subsequence。

原数列        5 2 9 4 8 3
＝＝＝＝＝＝＝＝＝＝＝＝＝＝
读入 5 |  1 |  5 			// 长度 1          （以 5 结尾最长的）
－－－－－－－－－－－－－－
读入 2 |  2 |    2   		// 长度 1          （以 3 结尾最长的）
－－－－－－－－－－－－－－
读入 9 |  3 |      9 		// 长度 1
　　  |  4 |    2 9 		// 长度 2，接第二串
　　  |  5 |  5   9 		// 长度 2，接第一串（以 9 结尾最长的）
－－－－－－－－－－－－－－
读入 4 |  6 |        4		// 长度 1
　　  |  7 |    2   4		// 长度 2，接第二串（以 4 结尾最长的）
－－－－－－－－－－－－－－
读入 8 |  8 |          8		// 长度 1
　　  |  9 |        4 8		// 长度 2，接第六串
　　  | 10 |    2     8		// 长度 2，接第二串
　　  | 11 |  5       8		// 长度 2，接第一串
　　  | 12 |    2   4 8		// 长度 3，接第七串（以 8 结尾最长的）
－－－－－－－－－－－－－－
读入 3 | 13 |            3	// 长度 1
　　  | 14 |    2       3	// 长度 2，接第二串（以 3 结尾最长的）

读入 5 |  5
读入 2 |  2
读入 9 |  2 9
读入 4 |  2 4	// 同时记录了第 4 串和第 7 串
读入 8 |  2 4 8
读入 3 |  2 3 8	// 同时记录了第 12 串和第 14 串

在这个排列顺序当中，长的 subsequence 排在短的 subsequence 之后，越串越长。

每当读入一个数字时，所有能串接的 subsequence，先前一定都出现过了──阵列裡也随时记录著先前出现过、比较优良的 subsequence。因此，运用 greedy，逐步地更新阵列资料，必可求出 LIS。

UVa 481

Longest Increasing Subsequence: Dynamic Programming

演算法

还有一种特别的方法可以找出 LIS。这个方法有一个限制，那就是给定的 sequence 的数字种类很少。

假设给定的 sequence，有一百个数字，但是只有五种不同的数字。对 sequence 中某一个位置的数字来说，它只可能接在这五种数字的其中一种数字后面；而所有 subsequence 的最后一个数字，也只有这五种可能。

有了这些特性，可以发现一个 greedy 方法。一、因为只有五种不同的数字──用五个变数，分别记录以该种数字做结尾的 subsequence 目前最长的长度。二、由左到右去读取 sequence，每次读进一个数字，就检查这个数字能不能让目前记录中的 subsequence 接得更长。三、要接得更长，就检查读进来的数字能不能分别接在那五种 subsequence 的后面，可以变长就加一。四、做完了一百个步骤之后，在五个变数之中，挑出最大的那个，就是 LIS 的长度。

用个实例来说明。假设给定的 sequence 是 1 1 2 3 4 5 4。这裡以 ss1 到 ss5，来代表以 1 到 5 结尾的 subseqeuence 目前最长的长度。

程式码。这裡将数字分为五种，并且利用函式来得到某一种数字的值、用值来知道数字属于哪一种。

Longest Increasing Subsequence: Dynamic Programming

Recurrence

这裡我们要讲解的是一种特别的 LIS 演算法，是把 LIS 的长度设计于状态当中，作为状态的其中一个维度，状态本身储存 LIS 的结尾数字。

根据 Robinson-Schensted-Knuth Algorithm，我们知道当下的 LIS 的结尾数字越小越好，如此就更有潜力将 LIS 接得更长。此处的方法即是运用了 Robinson-Schensted-Knuth Algorithm 的概念。

f(n, l) =  min( f(n-1, l), s[n] : if f(n-1, l-1) < s[n] )

f(n, l)：第 0 项到第 n 项，长度为 l 的递增子序列，最小的结尾数值。
s[n]：第 n 项数值。

也可以改用索引值来记录。这是比较适当的方式，只不过初始化会稍微麻烦一点。

f(n, l) =  min( f(n-1, l), n : if s[f(n-1, l-1)] < s[n] )

f(n, l)：第 0 项到第 n 项，长度为 l 的递增子序列，最小的结尾数值的索引值。
s[n]：第 n 项数值。

计算顺序是依序读取序列数值，然后每个数值都尝试能不能接得更长。

时间複杂度为 O(NL)，N 为数列长度，L 为 LIS 的长度。

计算 LIS 的长度

Non-Squashing Stack of Boxes

【注：这个问题还没有正式名称。】

有一堆封装完毕的纸箱，内容物的重量皆不同。现在要把纸箱一个一个叠起来存放，然而每个纸箱都有不同的抗压力量，如果一个纸箱上方的总重量，超过这个纸箱的抗压力量，这个纸箱就会被压伤，这是我们不乐见的。请问一次最多能叠多少个纸箱？又有多少种不会压坏纸箱的叠法呢？

【注：我有找到一个接近的问题，叫做 Sloane's Box Stacking Problem，提供各位参考。】

UVa 10154

延伸阅读

这个问题可以等价转换成单机排程问题，可参考“ Single Machine Scheduling, Minimize the Number of Tardy Jobs ”。

N 个工作要完成　　　　  <---> N 个箱子要叠
工作的处理时间　　　　 <---> 箱子的内容物重量
工作的完工期限　　　　 <---> 箱子的抗压力量＋箱子的内容物重量
如期完工的工作越多越好 <---> 箱子叠越多越好

第一种分割问题的方法：由上往下叠，累计重量越少越好。

一、依照承重能力由小到大排序。
二、依序叠纸箱，由上往下叠，求出 LIS。

在一个合理的叠法当中，任意两个紧邻的纸箱，如果上方纸箱的承重能力比下方纸箱还强，那麽交换这两个纸箱，仍是一个合理的叠法。也就是说，一次叠最多个纸箱的叠法，可以经过多次两两交换紧邻纸箱，使得由上往下来看，纸箱的承重能力恰好是递增的。也就是说，我们可以依照承重能力排序纸箱，再来求 LIS。

由上往下叠纸箱的过程当中，需要不断的累计纸箱的总重量，如果发现一个更好的叠法，就要更新总重量，并且让总重量越小越好，如此一来下方就可以更容易添上纸箱。添上纸箱的条件，是该纸箱能够承受上方全部纸箱的总重量，才能添上纸箱。