《編程之美》讀書筆記17： 2.16 求數(shù)組中最長遞增子序列
思路：每處理一個(gè)數(shù)，都可以將這個(gè)數(shù)插入到已經(jīng)找到的某個(gè)遞增子序列（假設(shè)包含無限個(gè)長度為0的空序列）后，使其長度增加1，處理完畢后，這些長度最大值即為所求。
具有相同長度i+1的遞增子序列，若這些序列的最后一個(gè)數(shù)最小值為min_v[i]，其所在的序列為A，則若某個(gè)數(shù)能插入到序列A后面，必然能插入到其它相同長度的遞增子序列后面，而能否插入到序列A后面，僅由min_v[i]值決定，因而只要維護(hù)min_v[i]值就夠了。
當(dāng)前數(shù)必然可以插入到某個(gè)長度為j（0<=j<=len， len為已找到的最長遞增子序列長度）的序列后，使得舊的min_v[j+1]（假設(shè)該數(shù)組每個(gè)值初始化為無窮大）大等于該數(shù)，必須更新min_v[j+1]等于該數(shù)。如果序列是嚴(yán)格遞增的，則只能找到一個(gè)這樣的j值；如果序列是非嚴(yán)格遞增的，可能找到不止一個(gè)j，取所有j值最大的即可，因?yàn)椴迦氲狡渌模?span lang=EN-US>min_v[j+1]值不會發(fā)生改變。
具體過程：
用min_v[i]保存當(dāng)前已找到的所有長度為i的遞增子序列的最后一個(gè)數(shù)的最小值。
用len保存當(dāng)前已找到的最長遞增子序列的長度。
對輸入src[n]， 顯然 min_v[0]=src[0]，這時(shí)len=1
從輸入數(shù)組的第二個(gè)數(shù)開始，(假設(shè)要求所求子序列嚴(yán)格遞增)
比較當(dāng)前值value和長度為len的子序列最后一個(gè)值(min_v[len-1])
1若value > min_v[len-1]，則可以將value加在已找到的最長遞增子序列后面,得到長度為len+1的更長的遞增子序列，即有min_v[len]=value，且len值加1。
2若value <= min_v[len-1]，則可以找到0<=j<=len-1滿足： value <= min_v[j]，
如果j=0，則value可組成長度為1的子序列，
如果j>0，則可以將value加在由min_v[j-1]決定的長度為j的子序列后，得到新的長度為j+1的子序列。
均有min_v[j]=value
如果要輸出一個(gè)最長遞增子序列，可以用一個(gè)數(shù)組info[i]記錄第i+1個(gè)src[n]數(shù)能得到最長遞增子序列的長度（info[i]等于前面要寫入value的位置在min_v的下標(biāo)加1）。再同時(shí)掃描一遍這兩個(gè)數(shù)組，從后往前掃描，先找到第一個(gè)對應(yīng)長度為len的數(shù)A，然后找到第一個(gè)對應(yīng)長度為len-1且比A小的數(shù)，以此類推找出所有的數(shù)。
size_t lis(const int src[], size_t sz)
{
if (src==NULL || sz<1) return 0;
//min_v[i]為當(dāng)前已找到的長度為i+1的所有遞增子序列的最后一個(gè)值的最小值。
vector<int> min_v(sz);
min_v[0]=src[0];
//len為當(dāng)前已找到的最長遞增子序列的長度
size_t i,len=1;
int value;
for (i=1; i<sz; ++i) {
value=src[i];
//假設(shè)遞增子序列是嚴(yán)格遞增
if (value>min_v[len-1]) min_v[len++]=value;
else *lower_bound(&min_v[0],&min_v[len], value)=value;
}
return len;
}