動态規劃求解最長遞增子序列的長度

一，問題描述

給定一個序列，求解它的最長 遞增 子序列 的長度。比如： arr[] = {3,1,4,1,5,9,2,6,5}   的最長遞增子序列長度為4。即為：1,4,5,9

二，算法分析

另一種方式是直接用DP求解，算法如下：時間複雜度為O(N^2)

①最優子問題

設lis[i] 表示索引為 [0...i] 上的數組上的 最長遞增子序列。初始時，lis[i]=1，注意，在DP中，初始值是很重要的，它是整個算法運作正确的關鍵。而初始值 則可以 通過 畫一個小的示例來 确定。

當 arr[i] > arr[j]，lis[i] = max{lis[j]}+1 ；其中，j 的取值範圍為：0,1...i-1

當 arr[i] < arr[j]，lis[i] = max{lis[j]} ；其中，j 的取值範圍為：0,1...i-1

②重疊子結構

從上面可以看出，計算 lis[i]時，需要計算 lis[j]，其中 j < i，這說明有重疊子問題。借用網路中一張圖如下：

而初始值 則可以 通過 畫一個小的示例來 确定。

參考資料：

<a href="http://www.cnblogs.com/hapjin/p/5572483.html">求解兩個字元串的最長公共子序列</a>

<a href="http://www.acmerblog.com/dp-3-longest-increasing-subsequence-4640.html" target="_blank">動态規劃(3)-最長遞增子序列</a>

三，代碼實作

錯誤版本1：

第13行if語句會導緻bug，arr[i]要大于 j belongs to  0,1,...i-1 中所有的 arr[j]中的最大值，并且 lis[i] 是該最大值 arr[j] 所對應的 lis[j] +1，而不是某個其他的arr[j] 對應的 lis[j]+1

正确完整版本：