求數(shù)組中最長(zhǎng)遞增子序列的解決方法
更新時(shí)間:2013年05月28日 17:27:15 作者:
本篇文章是對(duì)c++中求數(shù)組中最長(zhǎng)遞增子序列的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
存儲(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ù)無(wú)后效性的定義我們知道,將各階段按照一定的次序排列好之后,對(duì)于某個(gè)給定的階段狀態(tài)來(lái)說(shuō),它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策,而只能間接地通過(guò)當(dāng)前的這個(gè)狀態(tài)來(lái)影響。換句話說(shuō),每個(gè)狀態(tài)都是歷史的一個(gè)完整總結(jié)。
同樣的,仍以序列1,-1,2,-3,4,-5,6,-7為例,我們?cè)谡业?之后,并不關(guān)心4之前的兩個(gè)值具體是怎樣,因?yàn)樗鼘?duì)找到6沒(méi)有直接影響。因此,這個(gè)問(wèn)題滿足無(wú)后效性,可以通過(guò)使用動(dòng)態(tài)規(guī)劃來(lái)解決。
可以通過(guò)數(shù)字的規(guī)律來(lái)分析目標(biāo)串:1,-1,2,-3,4,-5,6,-7。
使用i來(lá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ì)求出后面的遞增序列沒(méi)有直接影響。(但是在其它情況下可能有影響)
依此類推之后,我們得出如下的結(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++代碼:
int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i < n; i++)
if(max < a[i])
max = a[i];
return max;
}
int LIS(vector<int> &array)
{
int *a = new int[array.size()];
for(int i = 0; i < array.size(); i++)
{
a[i] = 1;//初始化默認(rèn)的長(zhǎng)度
for(int j = 0; j < i; j++) //前面最長(zhǎng)的序列
{
if(array [i] > array [j] && a[j] + 1 > a[i]) //當(dāng)前數(shù)字比第j個(gè)大,且標(biāo)記數(shù)組需要更新
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}
這種方法的時(shí)間復(fù)雜度為O(N2 + N) = O(N2)
解法二
在前面的分析中,當(dāng)考察第i+1個(gè)元素的時(shí)候,我們是不考慮前面i個(gè)元素的分布情況的?,F(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]。
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());//b是存儲(chǔ)遞增序列長(zhǎng)度為k的最后元素下標(biāo)
//比如b[1]是存儲(chǔ)遞增子序列最大元素的最小值的下標(biāo)
//b是存儲(chǔ)最長(zhǎng)子序列的下標(biāo)
int u, v;
if (a.size() < 1)
return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++)
{
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) //二分搜索
{
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else v=c;
}
if (a[i] < a[b[u]])
{
if (u > 0)
p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
return b;
}
例如:在序列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ù)無(wú)后效性的定義我們知道,將各階段按照一定的次序排列好之后,對(duì)于某個(gè)給定的階段狀態(tài)來(lái)說(shuō),它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策,而只能間接地通過(guò)當(dāng)前的這個(gè)狀態(tài)來(lái)影響。換句話說(shuō),每個(gè)狀態(tài)都是歷史的一個(gè)完整總結(jié)。
同樣的,仍以序列1,-1,2,-3,4,-5,6,-7為例,我們?cè)谡业?之后,并不關(guān)心4之前的兩個(gè)值具體是怎樣,因?yàn)樗鼘?duì)找到6沒(méi)有直接影響。因此,這個(gè)問(wèn)題滿足無(wú)后效性,可以通過(guò)使用動(dòng)態(tài)規(guī)劃來(lái)解決。
可以通過(guò)數(shù)字的規(guī)律來(lái)分析目標(biāo)串:1,-1,2,-3,4,-5,6,-7。
使用i來(lá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ì)求出后面的遞增序列沒(méi)有直接影響。(但是在其它情況下可能有影響)
依此類推之后,我們得出如下的結(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++代碼:
復(fù)制代碼 代碼如下:
int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i < n; i++)
if(max < a[i])
max = a[i];
return max;
}
int LIS(vector<int> &array)
{
int *a = new int[array.size()];
for(int i = 0; i < array.size(); i++)
{
a[i] = 1;//初始化默認(rèn)的長(zhǎng)度
for(int j = 0; j < i; j++) //前面最長(zhǎng)的序列
{
if(array [i] > array [j] && a[j] + 1 > a[i]) //當(dāng)前數(shù)字比第j個(gè)大,且標(biāo)記數(shù)組需要更新
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}
這種方法的時(shí)間復(fù)雜度為O(N2 + N) = O(N2)
解法二
在前面的分析中,當(dāng)考察第i+1個(gè)元素的時(shí)候,我們是不考慮前面i個(gè)元素的分布情況的?,F(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]。
復(fù)制代碼 代碼如下:
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());//b是存儲(chǔ)遞增序列長(zhǎng)度為k的最后元素下標(biāo)
//比如b[1]是存儲(chǔ)遞增子序列最大元素的最小值的下標(biāo)
//b是存儲(chǔ)最長(zhǎng)子序列的下標(biāo)
int u, v;
if (a.size() < 1)
return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++)
{
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) //二分搜索
{
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else v=c;
}
if (a[i] < a[b[u]])
{
if (u > 0)
p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
return b;
}
相關(guān)文章
C++控制臺(tái)實(shí)現(xiàn)密碼管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++控制臺(tái)實(shí)現(xiàn)密碼管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-11-11VS2022 CUDA環(huán)境配置的實(shí)現(xiàn)步驟
本文主要介紹了VS2022 CUDA環(huán)境配置的實(shí)現(xiàn)步驟,文中通過(guò)圖文示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05C語(yǔ)言經(jīng)典例程100例(經(jīng)典c程序100例)
這篇文章主要介紹了C語(yǔ)言經(jīng)典例程100例,經(jīng)典c程序100例,學(xué)習(xí)c語(yǔ)言的朋友可以參考一下2018-03-03C++ STL關(guān)聯(lián)式容器自定義排序規(guī)則的2種方法
這篇文章主要介紹了C++ STL關(guān)聯(lián)式容器自定義排序規(guī)則的2種方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03C++實(shí)現(xiàn)自定義撤銷重做功能的示例代碼
在使用c++做界面開發(fā)的時(shí)候,尤其是實(shí)現(xiàn)白板功能時(shí)需要自己實(shí)現(xiàn)一套撤銷重做功能.如果是qt則有QUndoable對(duì)象,可以直接拿來(lái)用。但是如果是使用gdi繪圖,則可能需要自己實(shí)現(xiàn)了。本文就來(lái)用C++實(shí)現(xiàn)自定義撤銷重做功能,需要的可以參考一下2022-12-12