11.1 最长连续子序列问题

变种问题：如果原先的序列变成集合，需要寻找一个最大子集，让子集中的元素能够构成一个连续的序列：

11.2 区间合并问题   

    不可能存在线性复杂度O(n)的算法，因为在确定区间下界时，需要对所有区间的下届进行比较，即需要排序。可以用一个极端例子来帮助理解，加入所有区间都是[i,i+0.1]的形式，其中i是整数，那么这些区间的合并问题就是一个排序问题。

11.3 12球问题

    三个隐含信息：

    1）这是一个有12个不同的球的问题

    2）本质是24选1。这24种情况是第1个球轻，第2个球轻，...，第12个球轻，以及第1个球重，第2个球重，...，第12个球重。最后要从24种种确定一种情况

    3）用天平称，每次有3种结果，即左边轻、两边相等、左边重，分别用<，=和>来表示，产生的信息量可以区分3种状态（i.e. 1 trit 吹特）

    因为一次称重必须获得一吹特信息，这样三次3^3=27>24才可能成功（有些人按照直觉将球分两组称，无论是左边重还是右边重，第一次称重都只获得了一比特信息；或者是均分分成4组，先称两组，这样剩下的6个球还有12种状态，也不可行）。因此在第一次称重时，只能将12球分成3组。

    解：

    1）将12球分成3组并编号，1～4号、5～8号、9～12号各一组，然后拿前2组到天平称，得到<、=、>的3种结果

    2）这三种结果中的每一种都剩下8中情况，然后要通过2次称重完成8选1。如果左边轻，即<：剩下1～4轻，5～8重；如果平衡，即=：剩下9～12轻或9～12重；如果左边重，即>：剩下1～4重，5～8轻

    3）根据第一次称重结果，需要分两种情况：

        a）第一种情况，出现了“=”，即前8球都是好球，那么剩下8种可能，即9～12轻和9～12重，根据每吹特信息将可能情况的当前数量除以3的特点，将8种情况分为3-3-2共3组，另外还可以利用1～8号球是好球的信息。第二次称重时，把1～3号3个好球放在天平一侧，9～11号球放在另一侧，称得结果：9～11轻、9～11重和平衡，前2种情况分别对应3种不确定性。这样就又用1次称重，完成了将8种可能性减少到3种、3种、2种，第三次就很顺利了。比如9～11轻，那第三次称重时天平两侧分别放9，10号球即可，如图：

        b）第二种情况要复杂一些，即第一次称两边不平衡，假定1～4号比5～8号球要轻，那么仍然以一吹特区分三种情况来作为指导思想，将剩余8种可能：1～4轻、5～8重给尽量分成3-3-2这样的三组，这里的做法只是一种，如图11.3左侧所示。

    12球问题实质上是一道典型的分支判断和决策问题，需要沿着图论思想去做，并且可以通过该问题深入理解信息和编码原理。

11.4 天际线问题

11.5 最长回文问题

    中心扩散时间复杂度是O(n^2)，就不说了，最有效的方法是Manacher算法，不是十分直观，一般面试也不考，本质上是一个建立在递归基础上的动态规划算法。这个YouTube链接虽然有些咖喱味，但我觉得讲的是最好的：https://www.youtube.com/watch?v=V-sEwsca1ak

11.6 计算器问题

11.7 如何产生搜索结果的摘要（Snippets Generation）

    因为搜索殷勤对每一个关键词都建立了索引，利用索引，能很快地找到包含最多关键词的窗口：

11.8 寻找和等于k的子数组问题

    如果从第 1 个元素累加至 i 的和为 sum_i，从第 1 个元素累加到 j 的和为 sum_j，如果 sum_j - sum_i = k，那么从 [i+1, ..., j] 的元素就构成了和为 k 的子数组：

    解决该问题的关键有两个：

    1）从寻找和等于 k 的连续子数组变成寻找从头到 i 部分和等于 sum_j - k 的子数组。后一种之所以容易找，是因为它们总是从第一个元素开始累加

    2）用哈希表以部分和为索引存储相关信息，这样用 O(1) 时间就可以知道某个要找的数是否是前面已经见到过的部分和

    该问题还可以扩展为输出所有符合条件的子数组，而不仅仅给出数量。解决办法是在哈希表的数据项中记录部分和对应的子数组右边界的位置，比如在表11.10中，部分和为14的一项中，数据部分要记录 {2,3,4} 这三个右边界（从0开始），同样其他各项的数据部分分别记录各自子数组的右边界