存儲(chǔ)擴(kuò)展算法n2編程c 寫一個(gè)時(shí)間復(fù)雜度盡可能低的程序，求一個(gè)一維數(shù)組（N個(gè)元素）中的最長(zhǎng)遞增子序列的長(zhǎng)度。
例如：在序列1，-1，2，-3，4，-5，6，-7中，其最長(zhǎng)的遞增子序列為1，2，4，6 或者 -1,2,4,6。（編程之美P198-202）
分析與解法
根據(jù)題目的要求，求一維數(shù)組中的最長(zhǎng)遞增子序列，也就是找一個(gè)標(biāo)號(hào)的序列b[0],b[1],…,b[m](0 <= b[0] < b[1] < … < b[m] < N)，使得array[b[0]]<array[b[1]]<…<array[b[m]]。

解法一
根據(jù)無后效性的定義我們知道，將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)來說，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能間接地通過當(dāng)前的這個(gè)狀態(tài)來影響。換句話說，每個(gè)狀態(tài)都是歷史的一個(gè)完整總結(jié)。
同樣的，仍以序列1，-1，2，-3，4，-5，6，-7為例，我們?cè)谡业?之后，并不關(guān)心4之前的兩個(gè)值具體是怎樣，因?yàn)樗鼘?duì)找到6沒有直接影響。因此，這個(gè)問題滿足無后效性，可以通過使用動(dòng)態(tài)規(guī)劃來解決。
可以通過數(shù)字的規(guī)律來分析目標(biāo)串：1，-1，2，-3，4，-5，6，-7。
使用i來表示當(dāng)前遍歷的位置
當(dāng)i=1時(shí)，顯然，最長(zhǎng)的遞增序列為（1），序列長(zhǎng)度為1.
當(dāng)i=2是，由于-1<1。因此，必須丟棄第一個(gè)值后重新建立串。當(dāng)前的遞增序列為（-1），長(zhǎng)度為1。
當(dāng)i=3時(shí)，由于2>1,2>-1。因此，最長(zhǎng)的遞增序列為（1,2）,(-1,2),長(zhǎng)度為2。在這里，2前面是1還是-1對(duì)求出后面的遞增序列沒有直接影響。（但是在其它情況下可能有影響）
依此類推之后，我們得出如下的結(jié)論。
假設(shè)在目標(biāo)數(shù)組array[]的前i個(gè)元素中，最長(zhǎng)遞增子序列的長(zhǎng)度為L(zhǎng)IS[i]。那么，
LIS[i+1]=max{1,LIS[k]+1},  array[i+1]>array[k],  for any k <= i
即如果array[i+1]大于array[k],那么第i+1個(gè)元素可以接在LIS[k]長(zhǎng)的子序列后面構(gòu)成一個(gè)更長(zhǎng)的子序列。于此同時(shí)array[i+1]本身至少可以構(gòu)成一個(gè)長(zhǎng)度為1的子序列。
根據(jù)上面的分析，就可以得到代碼清單：
C++代碼：

這種方法的時(shí)間復(fù)雜度為O(N2 + N) = O(N2)

解法二
在前面的分析中，當(dāng)考察第i+1個(gè)元素的時(shí)候，我們是不考慮前面i個(gè)元素的分布情況的。現(xiàn)在我們從另一個(gè)角度分析，即當(dāng)考察第i+1個(gè)元素的時(shí)候考慮前面i個(gè)元素的情況。
對(duì)于前面i個(gè)元素的任何一個(gè)遞增子序列，如果這個(gè)子序列的最大的元素比array[i+1]小，那么就可以將array[i+1]加在這個(gè)子序列后面，構(gòu)成一個(gè)新的遞增子序列。
比如當(dāng)i=4的時(shí)候，目標(biāo)序列為1，-1，2，-3，4，-5，6，-7最長(zhǎng)遞增序列為(1,2),(-1,2)。
那么，只要4>2,就可以把4直接增加到前面的子序列中形成一個(gè)新的遞增子序列。
因此，我們希望找到前i個(gè)元素中的一個(gè)遞增子序列，使得這個(gè)遞增子序列的最大的元素比array[i+1]小，且長(zhǎng)度盡量地長(zhǎng)。這樣將array[i+1]加在該遞增子序列后，便可以找到以array[i+1]為最大元素的最長(zhǎng)遞增子序列。
仍然假設(shè)在數(shù)組的前i個(gè)元素中，以array[i]為最大元素的最長(zhǎng)遞增子序列的長(zhǎng)度為L(zhǎng)IS[i]。
同時(shí)，假設(shè)：
長(zhǎng)度為1的遞增子序列最大元素的最小值為MaxV[1];
長(zhǎng)度為2的遞增子序列最大元素的最小值為MaxV[2];
……
長(zhǎng)度為L(zhǎng)IS[i]的遞增子序列最大元素的最小值為MaxV[LIS[i]];

本循環(huán)不變式P是：
P：k是序列a[0:i]的最長(zhǎng)遞增子序列的長(zhǎng)度，0≤i＜n。
容易看出，在由i-1到i的循環(huán)中，a[i]的值起關(guān)鍵作用。如果a[i]能擴(kuò)展序列a[0;i-1]的最長(zhǎng)遞增子序列的長(zhǎng)度，則k=k+1，否則k不變。設(shè)a[0;i-1]中長(zhǎng)度為k的最長(zhǎng)遞增子序列的結(jié)尾元素是a[j](0≤j≤i-1)，則當(dāng)a[i]≥a[j]時(shí)可以擴(kuò)展，否則不能擴(kuò)展。如果序列a[0;i-1]中有多個(gè)長(zhǎng)度為k的最長(zhǎng)遞增子序列，那么需要存儲(chǔ)哪些信息？容易看出，只要存儲(chǔ)序列a[0;i-1]中所有長(zhǎng)度為k的遞增子序列中結(jié)尾元素的最小值b[k]。因此，需要將循環(huán)不變式P增強(qiáng)為：
P：0≤i＜n;k是序列a[0;i]的最長(zhǎng)遞增子序列的長(zhǎng)度；
b[k]是序列a[0;i]中所有長(zhǎng)度為k的遞增子序列中最小結(jié)尾元素值。
相應(yīng)地，歸納假設(shè)也增強(qiáng)為：已知計(jì)算序列a[0;i-1](i＜n)的最長(zhǎng)遞增子序列的長(zhǎng)度k以及序列a[0;i]中所有長(zhǎng)度為k的遞增子序列中的最小結(jié)尾元素值b[k]的正確算法。
增強(qiáng)歸納假設(shè)后，在由i-1到i的循環(huán)中，當(dāng)a[i]≥b[k]時(shí)，k=k+1，b[k]=a[i],否則k值不變。注意到當(dāng)a[i]≥b[k]時(shí)，k值增加，b[k]的值為a[i]。那么，當(dāng)a[i]＜b[k]時(shí)，b[l;k]的值應(yīng)該如何改變？如果a[i]<b[l],則顯然應(yīng)該將b[l]的只改變?yōu)閍[i],當(dāng)b[l]≤a[i]≤b[k]時(shí)，注意到數(shù)組b是有序的，可以用二分搜索算法找到下標(biāo)j，使得b[j-1]≤a[i]≤b[j]。此時(shí)，b[1;j-1]和b[j+1;k]的值不變，b[j]的值改變?yōu)閍[i]。