04. 試從含有n個(gè)int型數(shù)的數(shù)組中刪去若干個(gè)成分，使剩下的全部成分構(gòu)成一個(gè)不減的子序列。設(shè)計(jì)算法和編寫程序求出數(shù)組的不減子序列的長。
解：
從數(shù)組的第一個(gè)元素開始，順序考察數(shù)組的每個(gè)元素，當(dāng)數(shù)組的全部元素都被考察后才能求出數(shù)組的最長不減子序列的長。設(shè)數(shù)組為b[]，已考察了b[0]至b[i-1]的全部元素，求得當(dāng)前最長的不減子序列長為k。當(dāng)前正要考察b[i]是否會(huì)引起k值增大，依賴于b[i]是否會(huì)大于或等于b[0]至b[i-1]中某個(gè)最長不減子序列的終元素.b[0]至b[i-1]中可能有多個(gè)長為k的不減子序列。很顯然，在同樣長度的不減子序列中，只要保留那個(gè)子序列終元素最小的一個(gè)就足夠了。如有一變量保存有在b[0]至b[i-1]中長度為k的不減子序列最小的終元素，這樣在b[0]至b[i-1]中，是否有長度為k+1的不減子序列，依賴于b[i]是否大于等于那個(gè)長度為k的不減子序列的終元素值。
但當(dāng)b[i]小于那個(gè)長度為k的不減子序列最小的終元素的值時(shí)，如果在b[0]至b[i-1]中有長度為k-1的不減子序列，且該子序列的值不大于b[i]，這時(shí)因長度為k-1的不減子序列的終元素值小于等于b[i]，就得到一個(gè)終元素更小的長度為k的不減子序列。為能發(fā)現(xiàn)上述可能，就得保留長度為k-1的不減子序列的終元素。依此類推，為保留長為k-2,k-3等的不減子序列，相應(yīng)地也要為它們保留終元素的值。為此要引入一個(gè)數(shù)組變量，設(shè)為數(shù)組a[]，其第j個(gè)元素a[j]存放長為j的不減子序列的終元素的值。顯然，數(shù)組a[]中的元素也是不減的序列。利用這個(gè)性質(zhì)，在考察b[i]時(shí)，就能知道a[]中哪個(gè)元素需要改變。從最長子序列至最短子序列順序?qū)ふ医K元素小于等于b[i]的長為j的子序列，因b[i]大于等于長為j的不減子序列的終元素，找到了一個(gè)終元素更小的長為j+1的不減子序列，用b[i]作長為j+1的子序列的終止元素。當(dāng)j的值為k 時(shí)，已為長為k+1的子序列設(shè)定了終元素，這時(shí)最長不減子序列長k應(yīng)增1。通過以上分析，得到求最長不減子序列長的算法如下：
算法---求數(shù)組b[]的最長不減子序列長
{
置最長不減子序列長k為1；
用b[0]設(shè)置長為1的子序列的終止元素；
for(i=1;i {
以子序列長為k至1的順序?qū)ふ移浣K元素小于等于b[i]的長為j的子序列；
用b[i]作為長為j+1的子序列的終元素；
if(j==k)k++; /*最長不減子序列長k增1*/
}
}
程序代碼如下：
#include
#define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N];
#define n sizeof b/sizeof b[0]
void main()
{
int k,i,j;
a[1]=b[0];
k=1;
for(i=1;i {
for(j=k;j>=1&&a[j]>b[i];j--);
a[j+1]=b[i]; /*長為j+1的子序列的終元素存貯在a[j+1]*/
if(j==k) k++; /*最長不減子序列長k增1*/
}
printf("K = %d\n",k);
}
程序運(yùn)行結(jié)果如下：
k = 5
解：
從數(shù)組的第一個(gè)元素開始，順序考察數(shù)組的每個(gè)元素，當(dāng)數(shù)組的全部元素都被考察后才能求出數(shù)組的最長不減子序列的長。設(shè)數(shù)組為b[]，已考察了b[0]至b[i-1]的全部元素，求得當(dāng)前最長的不減子序列長為k。當(dāng)前正要考察b[i]是否會(huì)引起k值增大，依賴于b[i]是否會(huì)大于或等于b[0]至b[i-1]中某個(gè)最長不減子序列的終元素.b[0]至b[i-1]中可能有多個(gè)長為k的不減子序列。很顯然，在同樣長度的不減子序列中，只要保留那個(gè)子序列終元素最小的一個(gè)就足夠了。如有一變量保存有在b[0]至b[i-1]中長度為k的不減子序列最小的終元素，這樣在b[0]至b[i-1]中，是否有長度為k+1的不減子序列，依賴于b[i]是否大于等于那個(gè)長度為k的不減子序列的終元素值。
但當(dāng)b[i]小于那個(gè)長度為k的不減子序列最小的終元素的值時(shí)，如果在b[0]至b[i-1]中有長度為k-1的不減子序列，且該子序列的值不大于b[i]，這時(shí)因長度為k-1的不減子序列的終元素值小于等于b[i]，就得到一個(gè)終元素更小的長度為k的不減子序列。為能發(fā)現(xiàn)上述可能，就得保留長度為k-1的不減子序列的終元素。依此類推，為保留長為k-2,k-3等的不減子序列，相應(yīng)地也要為它們保留終元素的值。為此要引入一個(gè)數(shù)組變量，設(shè)為數(shù)組a[]，其第j個(gè)元素a[j]存放長為j的不減子序列的終元素的值。顯然，數(shù)組a[]中的元素也是不減的序列。利用這個(gè)性質(zhì)，在考察b[i]時(shí)，就能知道a[]中哪個(gè)元素需要改變。從最長子序列至最短子序列順序?qū)ふ医K元素小于等于b[i]的長為j的子序列，因b[i]大于等于長為j的不減子序列的終元素，找到了一個(gè)終元素更小的長為j+1的不減子序列，用b[i]作長為j+1的子序列的終止元素。當(dāng)j的值為k 時(shí)，已為長為k+1的子序列設(shè)定了終元素，這時(shí)最長不減子序列長k應(yīng)增1。通過以上分析，得到求最長不減子序列長的算法如下：
算法---求數(shù)組b[]的最長不減子序列長
{
置最長不減子序列長k為1；
用b[0]設(shè)置長為1的子序列的終止元素；
for(i=1;i
以子序列長為k至1的順序?qū)ふ移浣K元素小于等于b[i]的長為j的子序列；
用b[i]作為長為j+1的子序列的終元素；
if(j==k)k++; /*最長不減子序列長k增1*/
}
}
程序代碼如下：
#include
#define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N];
#define n sizeof b/sizeof b[0]
void main()
{
int k,i,j;
a[1]=b[0];
k=1;
for(i=1;i
for(j=k;j>=1&&a[j]>b[i];j--);
a[j+1]=b[i]; /*長為j+1的子序列的終元素存貯在a[j+1]*/
if(j==k) k++; /*最長不減子序列長k增1*/
}
printf("K = %d\n",k);
}
程序運(yùn)行結(jié)果如下：
k = 5