（1）最長遞增子序列問題

有兩種方法：（1）動態(tài)規(guī)劃方法（2）類似二分查找的方法O（nlogn）

動態(tài)規(guī)劃方法：

以i結(jié)尾的序列的最長遞增子序列和其[0, i - 1]“前綴”的最長遞增子序列有關(guān)，設(shè)LIS[i]保存以i結(jié)尾的最長遞增子序列的長度：
????若i = 0，則LIS[i] = 1；
? ? 若i > 0，則LIS[i]的值和其[0, i - 1]前綴的最長遞增子序列長度有關(guān)，用j遍歷[0, i - 1]得到其最長遞增子序列為LIS[j]，對每一個LIS[j]，如果序列array[j] ?< array[i]并且LIS[j] + 1 > LIS[i]，則LIS[i]的值變成LIS[j] + 1。即：
? ? LIS[i] = max{1, LIS[j] + 1}，其中array[i] > array[j] 且 j = [0, i - 1]。

代碼如下：

。。。。。晚上補充上

（2）采用類似二分查找方法

假設(shè)存在一個序列d[1...9] = 2 1 5 3 6 4 8 9 7，可以看出它的LIS長度是5。
? ? 下面一步一步試著找到它。
? ? 我們定義一個序列B，然后令i = 1 to 9逐個考察這個序列。
????此外，我們用一個變量len來記錄現(xiàn)在的最長算到多少。
? ? 首先，把d[1]有序的放到B中，令B[1] = 2，就是說當(dāng)只有一個數(shù)字2的時候，長度為1的LIS的最小末尾是2，這時len = 1；
? ? 然后，把d[2]有序的放到B中，令B[1] = 1，就是說長度為1的LIS的最小末尾是1，d[1] = 2已經(jīng)沒用了，很容易理解吧，這時len = 1；
? ? 接著，d[3] = 5，d[3] > B[1]，所以令B[1 + 1] = B[2] = d[3] = 5，就是說長度為2的LIS的最小末尾是5，很容易理解吧，這時B[1...2] = 1, 5，len = 2；
? ? 再來，d[4] = 3，它正好在1,5之間，放在1的位置顯然不合適，因為1小于3，長度為1的LIS最小末尾應(yīng)該是1，這樣很容易推知，長度為2的LIS最小末尾是3，于是可以把5淘汰掉，這時B[1...2] = 1,3，len = 2；
? ? 繼續(xù)，d[5] = 6，它在3的后面，因為B[2] = 3，而6在3后面，于是很容易推知B[3] = 6，這時B[1...3] = 1,3,6，還是很容易理解吧？這時len = 3；
? ? 第6個，d[6] = 4，你看它在3和6之間，于是就可以把6替換掉，得到B[3] = 4。B[1...3] = 1,3,4，這時len = 3；
? ? 第7個，d[7] = 8，它很大，比4大，于是B[4] = 8，這時len = 4；
? ? 第8個，d[8] = 9，得到B[5] = 9，len繼續(xù)增大，這時len = 5；
? ? 最后一個，d[9] = 7，它在B[3] = 4和B[4] = 8之間，所以我們知道，最新的B[4] = 7, B[1...5] = 1,3,4,7,9，len = 5。
? ? 于是我們知道了LIS的長度為5。
? ? 注意，注意。這個1,3,4,7,9不是LIS，它只是存儲了對應(yīng)長度LIS的最小末尾。有了這個末尾，我們就可以一個一個地插入數(shù)據(jù)。雖然最后一個 d[9] = 7更新進(jìn)去對于這個數(shù)組數(shù)據(jù)沒有什么意義，但是如果后面再出現(xiàn)兩個數(shù)字8和9，那么就可以把8更新到d[5]，9更新到d[6]，得到LIS的長度為6。
? ? 然后應(yīng)該發(fā)現(xiàn)一件事情了：在B中插入數(shù)據(jù)是有序的，而且進(jìn)行替換而不需要移動——也就是說，可以使用二分查找，將每一個數(shù)字的插入時間優(yōu)化到O(logn)，于是算法的時間復(fù)雜度就降低到了O(nlogn)了。

代碼如下：

?

1 int findlis(int *A,int n,int *lefttoright) //從左向右最長遞增子序列 2 { 3 if(A==NULL||n<0) 4 return -1; 5 int *lis=new int[n]; 6 //int *lefttoright=new int[n]; 7 lefttoright[0]=1; //lefttoright[i]保存從左到右，以i為終點的最長遞增子序列長度，注意已經(jīng)是正常的長度了，不是小一了 8 int max=0; //max是lis[]的最大下標(biāo)如lis[]={1,2,4}時,max=2; 9 lis[0]=A[0]; 10 for(int i=1;i<n;i++) 11 { 12 int left=0; 13 int right=max; 14 while(left<=right) //這個二分查找就是最終left落到指定位置例如lis[]={1,2,4},若A[i]=5，left=3（從0開始），則更新為lis[]={1,2,4,5}；lis[]={1,2,4},若A[i]=3，left=2,則更新為lis[]={1,2,3}； 15 { 16 int mid=(left+right)/2; 17 if(A[i]>lis[mid]) 18 left=mid+1; 19 else 20 right=mid-1; 21 } 22 lis[left]=A[i]; 23 lefttoright[i]=left+1; //lefttoright[i]等于left加一，同返回時是max+1同樣道理 24 if(left>max) //如果left>max，則讓max=left 25 max++; 26 } 27 delete lis; 28 return max+1; //注意，必須返回max+1，才是最終結(jié)果max是最長遞增子序列長度減一 29 }

下面就開始實現(xiàn)“從一列數(shù)中篩除盡可能少的數(shù)使得從左往右看，這些數(shù)是從小到大再從大到小的“這個問題。
雙端LIS問題，用動態(tài)規(guī)劃的思想可以解決，目標(biāo)規(guī)劃函數(shù)為max{B[i] + C[i] - 1}，其中B[i]是從左到右的，0~i個數(shù)之間滿足遞增的數(shù)字個數(shù)；C[i]為從右到左的，n- 1 ~ i個數(shù)之間滿足遞增的數(shù)字個數(shù)。最后結(jié)果為n- max + 1，其中動態(tài)規(guī)劃的時候，可以用二分查找進(jìn)行處理，如上述求最長遞增子序列的方法二。
代碼如下： 1 #include <iostream> 2 using namespace std; 3 4 //最長遞增子序列的O（nlogn）方法 5 //lis[i]表示最長遞增子序列的長度的i+1的最小的最后一個元素 6 7 int findlis(int *A,int n,int *lefttoright) //從左向右最長遞增子序列 8 { 9 if(A==NULL||n<0) 10 return -1; 11 int *lis=new int[n]; 12 //int *lefttoright=new int[n]; 13 lefttoright[0]=1; //lefttoright[i]保存從左到右，以i為終點的最長遞增子序列長度，注意已經(jīng)是正常的長度了，不是小一了 14 int max=0; //max是lis[]的最大下標(biāo)如lis[]={1,2,4}時,max=2; 15 lis[0]=A[0]; 16 for(int i=1;i<n;i++) 17 { 18 int left=0; 19 int right=max; 20 while(left<=right) //這個二分查找就是最終left落到指定位置例如lis[]={1,2,4},若A[i]=5，left=3（從0開始），則更新為lis[]={1,2,4,5}；lis[]={1,2,4},若A[i]=3，left=2,則更新為lis[]={1,2,3}； 21 { 22 int mid=(left+right)/2; 23 if(A[i]>lis[mid]) 24 left=mid+1; 25 else 26 right=mid-1; 27 } 28 lis[left]=A[i]; 29 lefttoright[i]=left+1; //lefttoright[i]等于left加一，同返回時是max+1同樣道理 30 if(left>max) //如果left>max，則讓max=left 31 max++; 32 } 33 delete lis; 34 return max+1; //注意，必須返回max+1，才是最終結(jié)果max是最長遞增子序列長度減一 35 } 36 37 int findrighttoleftincrease(int *A,int n,int * righttoleft) //從右向左最長遞增子序列，也可以說成是從左向右最長遞減子序列 38 { 39 if(A==NULL||n<0) 40 return -1; 41 int *lis=new int[n]; 42 //int *righttoleft=new int[n]; 43 lis[0]=A[n-1]; //lis[0]=為A【n-1] 44 righttoleft[n-1]=1; //注意是lefttoright[n-1]=1 45 int max=0; 46 int left,right; 47 for(int i=n-2;i>=0;i--) 48 { 49 left=0; 50 right=max; 51 while(left<=right) 52 { 53 int mid=(left+right)/2; 54 if(A[i]>lis[mid]) 55 left=mid+1; 56 else 57 right=mid-1; 58 } 59 lis[left]=A[i]; 60 righttoleft[i]=left+1; 61 if(left>max) //其實這時，max++后，max==left 62 max++; 63 } 64 delete lis; 65 return max++; 66 } 67 68 69 int main() 70 { 71 //網(wǎng)易的去掉最少元素使得從左向右遞增然后遞減，即為從左向右遞增然后遞減的最大值 72 //Big=max（lefttoright[i]+righttoleft[i]-1} 73 //所求即為n-Big。 74 int A[]={2,3,5,1,6,9,10,15,1}; 75 int *lefttoright=new int[9]; 76 int *righttoleft=new int[9]; 77 int maxleft=findlis(A,9,lefttoright); 78 if(maxleft==-1) 79 cout<<"wrong"<<endl; 80 else 81 cout<<"max num lefttoright= "<<maxleft<<endl; 82 int maxright=findrighttoleftincrease(A,9,righttoleft); 83 if(maxright==-1) 84 cout<<"wrong"<<endl; 85 else 86 cout<<"max num righttoleft= "<<maxright<<endl; 87 int max=0; 88 for(int i=0;i<9;i++) 89 { 90 if(lefttoright[i]+righttoleft[i]-1>max) 91 max=lefttoright[i]+righttoleft[i]-1; 92 } 93 cout<<"去除"<<9-max<<endl; 94 delete lefttoright; 95 delete righttoleft; 96 system("pause"); 97 }

完。

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zmlctt/p/3842501.html

總結(jié)

以上是生活随笔為你收集整理的最长递增子序列和网易去除最少使从左向右递增又递减问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。