# 最長遞增子序列 [http://blog.csdn.net/lisonglisonglisong/article/details/45241965](http://blog.csdn.net/lisonglisonglisong/article/details/45241965) 最長遞增子序列（Longest Increasing Subsequence）是指找到一個給定序列的最長子序列的長度，使得子序列中的所有元素單調遞增。 例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，長度為 4。 ### 解法一：轉化為求最長公共子序列 其實可以把 求最長遞增子序列問題 轉化為 求最長公共子序列的問題。 - 設數組 { 3， 5， 7， 1， 2， 8 } 為 A - 對數組 A 排序，排序后的數組為 B = { 1， 2， 3， 5， 7， 8 }。 - 于是，求數組 A 的最長遞增子序列，就是求數組 A 與數組 B 的最長公共子序列。 最長公共子序列的求法見《[動態規劃DP](http://blog.csdn.net/lisonglisonglisong/article/details/41548557)》。本方法的時間復雜度是 Θ(nlgn)+Θ(n2)=Θ(n2) ### 解法二：動態規劃法 雖然解法一也是使用動態規劃，但是與解法一不同的是，解法二不進行轉化，而是直接在原問題上采用動態規劃法。 **最優子結構：** 對于長度為 N 的數組 A[N]={a0,a1,a2,…,an?1}，假設我們想求以ai 結尾的最大遞增子序列長度，設為L[i]，那么 L[i]=???max(L[j])+1,1,where?j<i?and?A[j]<A[i]otherwise 也就是 j 的范圍是 0 到 i–1。這樣，想求ai 結尾的最大遞增子序列的長度，我們就需要遍歷 i 之前的所有位置 j（0到 i-1），找出A[j]<A[i]，計算這些j 中，能產生最大 L[j] 的 j，之后就可以求出L[i]。之后對每一個A[N]中的元素都計算以他們各自結尾的最大遞增子序列的長度，這些長度的最大值，就是我們要求的問題——數組A的最大遞增子序列的長度。 **重疊子問題：** 根據上述推導式采用遞歸實現的話，有些子問題會被計算很多次。 **動態規劃法：** 綜上所述，LIS 問題具有動態規劃需要的兩個性質，可以使用動態規劃求解該問題。設數組 A = { 3，5，7，1，2，8 }，則：  具體的打表方式如下： - 初始化對角線為 1； - 對每一個 i，遍歷 j（0 到 i-1）： - 若`A[i] <= A[j]`，置 1。 - 若`A[i] > A[j]`，取第 j 行的最大值加 1。 打完表以后，最后一行的最大值就是最長遞增子序列的長度。由于每次都進行遍歷，故時間復雜度還是 Θ(n2)。 [](http://blog.csdn.net/lisonglisonglisong/article/details/45241965) ~~~ // LIS 的動態規劃方式實現 #include <iostream> using namespace std; int getLISLength(int A[], int len) { //定義一維數組并初始化為1 int* lis = new int[len]; for (int i = 0; i < len; ++i) lis[i] = 1; // 計算每個i對應的lis最大值，即打表的過程 for (int i = 1; i < len; ++i) for (int j = 0; j < i; ++j) // 0到i-1 if ( A[i] > A[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; // 更新 // 數組中最大的那個，就是最長遞增子序列的長度 int maxlis = 0; for (int i = 0; i < len; ++i) if ( maxlis < lis[i] ) maxlis = lis[i]; delete [] lis; return maxlis; } ~~~ ### 解法三：Θ(nlgn)的方案 本解法的具體操作如下： - 建立一個輔助數組array，依次讀取數組元素 x 與數組末尾元素 top比較： - 如果 x > top，將 x 放到數組末尾； - 如果 x < top，則二分查找數組中第一個 大于等于x 的數，并用 x 替換它。 遍歷結束之后，最長遞增序列長度即為棧的大小。 注意c數組的下標代表的是子序列的長度，c數組中的值也是按遞增順序排列的。這才可能用二分查找。 數組array[i]存儲的是子序列長度為i的序列最后一個值（該值是該子序列中最大的元素；如果長度為i的序列有多個，那么array[i]存放這類序列最后元素中的最小一個） ~~~ int getLISLength(int num[], int length) { ?vector<int> ivec; ?for (int i = 0; i < length; ++i) { ??? ?if (ivec.size() == 0 || ivec.back() < num[i]) ??? ??? ?ivec.push_back(num[i]); ??? ?else { ??? ??? ?int low = 0, high = ivec.size() - 1; ??? ??? ?while (low < high) { ??? ??? ??? ?int mid = (low + high) / 2; ??? ??? ??? ?if (ivec[mid] < num[i]) ??? ??? ??? ??? ?low = mid + 1; ??? ??? ??? ?else ??? ??? ??? ??? ?high = mid - 1; ??? ??? ?} ??? ??? ?ivec[low] =? num[i]; ??? ?} ?} ?return ivec.size(); } ~~~ 特別注意的是：本方法只能用于求最長遞增子序列的長度，輔助數組中的序列不是最長遞增子序列： - 例一：原序列為1，5，8，3，6，7 輔助數組為1，5，8，此時讀到3，用3替換5，得到1，3，8； 再讀6，用6替換8，得到1，3，6；再讀7，得到最終棧為1，3，6，7。最長遞增子序列為長度4。 - 例二：原序列為1，5，8，3 則最棧輔助數組為1，3，8。明顯這不是最長遞增子序列！ # 合唱隊問題 <table id="table1" class="grid grid_tb " border="0" cellpadding="0" cellspacing="0"><tbody><tr><td class="grid_left_td" width="10%">描述:?</td><td width="90%"><p style="white-space:normal">計算最少出列多少位同學，使得剩下的同學排成合唱隊形</p><p style="white-space:normal">說明：</p><p style="white-space:normal"><span style="font-family:'times new roman'">N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。?<br/>合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK，???則他們的身高滿足存在i（1&lt;=i&lt;=K）使得Ti&lt;T2&lt;......&lt;Ti-1&lt;Ti&gt;Ti+1&gt;......&gt;TK。?<br/>?????你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。?<br/></span></p><p style="white-space:normal">?</p><p><br/></p>?</td></tr><tr><td class="grid_left_td">知識點:</td><td>?循環?</td></tr><tr><td class="grid_left_td">題目來源:</td><td>?內部整理?</td></tr><tr><td class="grid_left_td">練習階段:</td><td>?初級?</td></tr><tr><td class="grid_left_td">運行時間限制:</td><td>無限制</td></tr><tr><td class="grid_left_td">內存限制:</td><td>無限制</td></tr><tr><td class="grid_left_td">輸入:</td><td>?<p style="white-space:normal">整數N</p><p style="white-space:normal">一行整數，空格隔開，N位同學身高</p><p><br/></p>?</td></tr><tr><td class="grid_left_td">輸出:</td><td>?<p><span style="font-family:'times new roman'">最少需要幾位同學出列</span><br/></p>?</td></tr><tr><td class="grid_left_td">樣例輸入:</td><td><pre>8 186 186 150 200 160 130 197 200 </pre></td></tr><tr><td class="grid_left_td">樣例輸出:</td><td><pre>4 </pre></td></tr></tbody></table> 根據題意可知，我們需要求出一個“中間點”，使得其左邊的【最長遞增子序列】和其右邊的【最長遞減子序列】之和最大。 ~~~ #include <iostream> #include <vector> using namespace std; int LonggestIncreaseLength(vector<int> &vec) { vector<int> result(vec.size(), 1); vector<int> result2(vec.size(), 1); for (int i = 1; i < vec.size(); i++) { for (int j = 0; j < i; j++) { if (vec[i] > vec[j] && result[i] < result[j] + 1) result[i] = result[j] + 1; } } for (int i = vec.size() - 2; i >= 0; --i) { for (int j = vec.size() - 1; j > i; --j) { if (vec[i] > vec[j] && result2[i] < result2[j] + 1) result2[i] = result2[j] + 1; } } int max = 0; for (int i = 0; i < vec.size(); i++) { if (max < result[i] + result2[i]) max = result[i] + result2[i]; } return vec.size() - max + 1; } int main() { int n; cin >> n; if (n <= 0) return 0; vector<int> ivec(n); for (int i = 0; i < n; i++) cin >> ivec[i]; cout << LonggestIncreaseLength(ivec) << endl; } ~~~