最長遞增子序列問題：

給定一個長度為N的數組，給定一個長度為N的數組，找出一個最長的單調自增子序列（不一定連續，但是順序不能亂）。例如：給定一個長度為6的數組A{5， 6， 7， 1， 2，8}，則其最長的單調遞增子序列為{5，6，7，8}，長度為4。

​

動態規劃做法(時間複雜度O(N^2))

假設我們定義一個大小為n的數組a，每個元素的值分別為a[0],a[1],....,a[n-1]。

我們將dp[i]表示為以下標為i結尾的最長遞增子序列長度，那麼dp[i]的值就等於從數組開始位置到i-1位置處找到的最大的dp[j]（0

算法流程：

從數組頭到尾遍歷每個位置i，根據i往前找所有滿足a[i]≥a[j]要求的j，且找到對應的dp[j]最大的哪一個j位置。遍歷完整個數組之後，得到整個dp數組中最大的那個dp[j]便是最長遞增子序列的長度。

例子：

時間複雜度：

由於要遍歷一遍數組，而且遍歷到每個位置i時還要往前找到最大的dp[j]（0

核心代碼：

利用二分法(時間複雜度為O(NlogN))

動態規劃的方法時間複雜度稍高，我們也可以利用二分法得出最長遞增子序列的長度。

算法流程：

定義數組a = {5，6，7，1，2，8}

定義一個變長的臨時數組tempArr，要求該數組的元素從小到大排序。

1）遍歷到5，數組tempArr為空，直接加入tempArr中。

2）遍歷到6，由於6大於數組中最後一個元素5，6直接加到數組後面。

3）遍歷到7，由於7大於數組中最後一個元素6，7直接加到數組後面。

4）遍歷到1，1小於數組中最後一個元素7，此時要在tempArr數組中找到>1最左邊的元素，找到為5，然後替換掉。因為既然可以以5來往後找最長連續遞增子序列，那為什麼不拿1來找呢？所以這就是算法的核心

5）遍歷到2，同樣由於2<7，所以找到>2最左邊的數，為6，替換，理由同上。

6）遍歷到8，由於8>7，所以直接插入。

算法結束，最長連續遞增子序列就是此時tempArr數組中的長度，為4.

整個過程如下圖所示

可以看出，整個算法的核心為遍歷每一個數k，然後判斷k和tempArr數組中最後一個數誰大，如果k大於或者等於tempArr數組中最後一個數，則直接插入tempArr中，如果k小於tempArr數組中最後一個數，則在tempArr中找到>k的最左邊的那個數，然後用k替換掉。

時間複雜度

那麼在元素遞增數組tempArr中找>k最左邊的那個數的時候，便可以使用二分法加速該過程。因此時間複雜度為O(NlogN)。

核心代碼

閱讀更多 IT界的泥石流 的文章

關鍵字: 算法 給定 數組