最长递增子序列问题（算法导论作业15.4-5、15.4-6）
问题描述
给定一个长度为n的数据系列S（索引从1到n），确定其中最长的一个递增子系列，并确保该系列中的所有元素依次递增）。
15.4-5、时间复杂度O(n^2)
初次见到这道题时, 我灵机一动想到一个简便方法. 在课本相关章节中, 讨论了LCS算法, 因此我们可以直接将这个序列排序O(nlogn), 然后将排序后的序列与原序列求LCS O(n^2), 从而得到所需的结果. 同学提醒后发现, 由于序列中可能存在重复元素, 所求子序列只能保证非递减而非严格递增. 因此不得不采用动态规划方法来解决这个问题.
子问题划分
定义 seq_i 为以 S_i 结尾的最长递增子序列之长度，则该序列的整体最长长度即为 max{seq_1, seq_2, ..., seq_n}。要确定 seq_i 的值，则需在 S_1 到 S_{i−1} 中寻找所有小于当前元素 S_i 的那些项，并取这些项所对应的 seq 值中的最大者加一。
seq[i] = max{0，seq[k]}+1，其中1<=k<i且S[k]<S[i]；
解的构造
很显然取seq数组中的最大值（max{seq[i]}），其中i从1到n（1<=i<=n），即为此问题最长递增子序列的长度（length）。接下来将该序列从数组末尾向始端扫描（从尾向前扫描），找到第一个位置j使得seq[j]等于当前的最大值（即找到第一个seq[j]= length）。此时该位置j对应的s[j]即为此子序列的最后一项（则s[j]就是这个子序列的最后一个元素）。随后将当前的最大值减少1（length--），并继续向前寻找倒数第二个元素的位置（继续向前输出倒数第二个元素）。
伪代码
//求数组seq[1...n]
for i = 1 to n do
max = 0;
for j = 1 to i do
if(S[j] < S[i} && seq[j] > max)
max = seq[j];
seq[i] = max + 1;
//求子序列长度
length = 0;
for i = 1 to n do
if(seq[i] > length)
length = seq[i];
//倒序输出子序列
k = length;
for i = n to 1 do
if(seq[i] = k)
print S[i];
k--;
return length;
AI写代码15.4-6时间复杂度O(nlogn)
书中说明：第i个递增子序列的末位数值必然大于其对应的第(i+1)个递增子序列的末位数值。
举例说明集合S={3 1 2 4}\text{\{}3, 1, 2, 4\text{\}}；其中具有两个元素的所有递增子序列为\text{\{}1, 2\text{\}}其最后一个元素是2 \text{\{}}或者\text{{}}\text{{}}\text{{}}\text{{}}\text{\{}}\text{{}}\text{\{}\text{\{}\}}\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquaud还有$\text{\{}$}$\text{\{}\text{{}}}$$\qquaud这些情况中的最后一个元素都是\displaystyle 4. 这一结论显而易见成立 因此对于任何一个长度为i+1 的递增子序列 我们都可以观察到它的前is个位置所构成的部分必然形成了一个长度为is的严格递增排列 而且第is个位置上的数值必定小于第i+1s个位置上的数值
字问题划分
令element[i]表示i长递增子序列中的最小尾元素。基于上述推论可知，elem[1...length]必然是严格递增序列。
遍历整个序列S，在遍历至第i个元素时，如果当前子序列的最大值elem[length]小于当前元素S[i]，则将当前子序列的最大值更新为该元素值；否则，在当前子序列的最大值不小于该元素的情况下（即(elem[length]>= S_i)），找到第一个大于或等于该元素的位置k，并将该位置处的记录更新为当前元素。
给定集合S=\{3,1,4,5,2\}时，在i=1的情况下有elem=\{3\}；当i=2时有elem=\{1\}；此时elem代表的是长度为1的最小子序列末尾元素值为1；而当i=3时有elem=\{1,4\}；这表明此时存在两种可能性：一是长度为1的情况末尾元素仍为1；另一种情况则是出现了一个新值即末尾元素变为4；继续下去当i=4和i=5时相应的结果也会随之变化。经过整个扫描过程后 elem 的总数量即为我们所求最长最小子序列的数量 但需要注意的是 并非由 elem 构成的就是所需的最长最小子序列
解的构造
自尾向前扫描S[1...n]，找到的elem[k]<=S[i]<elem[k+1]，即为子序列第k个元素。
考虑集合S={3, 1, 4, 5, 2}以及元素列表elem={1, 2, 5}并附加一个占位符元素以辅助排序过程。在处理过程中：
- 当索引i等于0时，在条件成立的情况下（即当前元素小于下一个元素），子序列的第一项确定为值3；
- 当索引i等于1时，在条件成立的情况下（即当前元素小于下一个元素），子序列的第二项确定为值1；
- 当索引i等于2时，在条件成立的情况下（即当前元素小于下一个元素），子序列的第三项确定为值4；
- 当索引i等于3时，在条件成立的情况下（即当前元素小于下一个元素），子序列的第四项确定为值5；
- 最后一项无需处理。
伪代码
elem[1] = S[1];
length = 1；
for i = 2 to n do
if(S[i] > elem[length])
elem[++length] = S[i];
eles
loc = Bi_Search(elem,length,S[i])//用二分查找找到位置
elem[loc] = S[i];
k = length;
elem[k+1] = +∞；//哨兵
//倒序输出子序列
for i = n to 1 do
if(elem[k]<=S[i]<elem[k+1])
print S[i];
k--;
if(k==0)
break;
return length;
AI写代码显然，对有序序列的二分查找时O(logn)，故整个算法的复杂度是O(nlogn)