11.1 最長連續(xù)子序列問題

變種問題：如果原先的序列變成集合，需要尋找一個最大子集，讓子集中的元素能夠構成一個連續(xù)的序列：

11.2 區(qū)間合并問題? ?

????不可能存在線性復雜度O(n)的算法，因為在確定區(qū)間下界時，需要對所有區(qū)間的下屆進行比較，即需要排序。可以用一個極端例子來幫助理解，加入所有區(qū)間都是[i,i+0.1]的形式，其中i是整數(shù)，那么這些區(qū)間的合并問題就是一個排序問題。

11.3 12球問題

????三個隱含信息：

????1）這是一個有12個不同的球的問題

????2）本質是24選1。這24種情況是第1個球輕，第2個球輕，...，第12個球輕，以及第1個球重，第2個球重，...，第12個球重。最后要從24種種確定一種情況

????3）用天平稱，每次有3種結果，即左邊輕、兩邊相等、左邊重，分別用<，=和>來表示，產(chǎn)生的信息量可以區(qū)分3種狀態(tài)（i.e. 1 trit 吹特）

????因為一次稱重必須獲得一吹特信息，這樣三次3^3=27>24才可能成功（有些人按照直覺將球分兩組稱，無論是左邊重還是右邊重，第一次稱重都只獲得了一比特信息；或者是均分分成4組，先稱兩組，這樣剩下的6個球還有12種狀態(tài)，也不可行）。因此在第一次稱重時，只能將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）根據(jù)第一次稱重結果，需要分兩種情況：

????????a）第一種情況，出現(xiàn)了“=”，即前8球都是好球，那么剩下8種可能，即9～12輕和9～12重，根據(jù)每吹特信息將可能情況的當前數(shù)量除以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號球要輕，那么仍然以一吹特區(qū)分三種情況來作為指導思想，將剩余8種可能：1～4輕、5～8重給盡量分成3-3-2這樣的三組，這里的做法只是一種，如圖11.3左側所示。

????12球問題實質上是一道典型的分支判斷和決策問題，需要沿著圖論思想去做，并且可以通過該問題深入理解信息和編碼原理。

11.4 天際線問題

11.5 最長回文問題

? ? 中心擴散時間復雜度是O(n^2)，就不說了，最有效的方法是Manacher算法，不是十分直觀，一般面試也不考，本質上是一個建立在遞歸基礎上的動態(tài)規(guī)劃算法。這個YouTube鏈接雖然有些咖喱味，但我覺得講的是最好的：https://www.youtube.com/watch?v=V-sEwsca1ak

11.6 計算器問題

11.7 如何產(chǎn)生搜索結果的摘要（Snippets Generation）

????因為搜索殷勤對每一個關鍵詞都建立了索引，利用索引，能很快地找到包含最多關鍵詞的窗口：

11.8 尋找和等于k的子數(shù)組問題

????如果從第 1 個元素累加至 i 的和為 sum_i，從第 1 個元素累加到 j 的和為 sum_j，如果 sum_j - sum_i = k，那么從 [i+1, ..., j] 的元素就構成了和為 k 的子數(shù)組：

????解決該問題的關鍵有兩個：

????1）從尋找和等于 k 的連續(xù)子數(shù)組變成尋找從頭到 i 部分和等于 sum_j - k?的子數(shù)組。后一種之所以容易找，是因為它們總是從第一個元素開始累加

????2）用哈希表以部分和為索引存儲相關信息，這樣用 O(1)?時間就可以知道某個要找的數(shù)是否是前面已經(jīng)見到過的部分和

????該問題還可以擴展為輸出所有符合條件的子數(shù)組，而不僅僅給出數(shù)量。解決辦法是在哈希表的數(shù)據(jù)項中記錄部分和對應的子數(shù)組右邊界的位置，比如在表11.10中，部分和為14的一項中，數(shù)據(jù)部分要記錄 {2,3,4} 這三個右邊界（從0開始），同樣其他各項的數(shù)據(jù)部分分別記錄各自子數(shù)組的右邊界