?

問題描述
????????對于一串數(shù)A={a1a2a3…an}，它的子序列為S={s1s2s3…sn}，滿足{s1<s2<s3<…<sm}。求A的最長子序列的長度。

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

算法描述：
????????設(shè)數(shù)串的長度為n，L[i]為以第i個數(shù)為末尾的最長上升子序列的長度，a[i]為數(shù)串的第i個數(shù)。
????????L[i]的計算方法為：從前i-1個數(shù)中找出滿足a[j]<a[i]（1<=j<i）條件的最大的L[j]，L[i]等于L[j]+1。
動態(tài)規(guī)劃表達式：

代碼實現(xiàn)：

int LIS(int a[], int n) {int len[MAXSIZE];int i, j;int maxlen = 0;//計算以第i個數(shù)為結(jié)尾的最長上升子序列的長度for (i = 1; i <= n; i++){len[i] = 0;//從前i-1個數(shù)中找出滿足a[j]<a[i]（1<=j<i）條件的最大的L[j]for (j = i-1; j >= 1; j--){if (a[j] < a[i] && len[j] > len[i]){len[i] = len[j];}}len[i]++;if (len[i] > maxlen){maxlen = len[i];}}return maxlen; }

上述算法的時間復(fù)雜度為O(n2)。

改進算法：
????????在從前i-1個數(shù)中找出滿足a[j]<a[i]（1<=j<i）條件的最大的L[j]的時間復(fù)雜度為O(n)，這里采用二分查找的方法對它進行優(yōu)化，使其復(fù)雜度降為O(nlogn)。
????????增設(shè)一個m[]數(shù)組，m[x]存放長度為x的最長上升子序列的最小末尾數(shù)。例：m[3] = 17表示長度為3的最長上升子序列的最小末尾數(shù)為17。
????????由于子序列是上升的，所以m數(shù)組中的元素有一個性質(zhì)，當x<y時，m[x]<m[y]，利用這個性質(zhì)來使用二分查找。
設(shè)m數(shù)組所存儲的最長上升子序列的長度為k，當前計算的數(shù)為第i個
如果a[i]>m[k]，則m[++k]=a[i]；
否則在m[1~k]內(nèi)二分查找小于（等于）a[i]的最大值的位置p，m[p]=a[i]。

代碼實現(xiàn)：

int BSearch(int a[], int n, int t) {int low = 1;int high = n;while (low <= high){int mid = (low + high) / 2;if (t == a[mid]){return mid;}else if (t > a[mid]){low = mid + 1;}else{high = mid - 1;}}return low; }int LIS_BSearch(int a[], int m[], int n) {int maxlen = 1;?? ??? ?//最長上升子序列的長度m[maxlen] = a[1];int i;for (i = 2; i <= n; i++){if (a[i] > m[maxlen]){m[++maxlen] = a[i];}else{//返回小于a[i]的最大值的位置pint p = BSearch(m, maxlen, a[i]);m[p] = a[i];}}return maxlen; }

改進后的算法時間復(fù)雜度為O(nlogn)。
?

總結(jié)

以上是生活随笔為你收集整理的最长上升子序列（Longest increasing subsequence）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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