最長序列演算法

1. 最長公共序列(LCS)演算法用c如何實現！

int **lcs_length(char p[],char q[],int **c,int **k,int m,int n)
{
int i,j;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(p[i-1]==q[j-1])//如果兩個字母相等的情況
{
c[i][j]=c[i-1][j-1]+1;
k[i][j]=1;
}
else
{
if(c[i-1][j]>=c[i][j-1])//兩字母不等情況1
{
c[i][j]=c[i-1][j];
k[i][j]=2;
}
else//兩字母不等情況2
{
c[i][j]=c[i][j-1];
k[i][j]=3;
}
}
}
}
return c,k;
}
輸出代碼
void print_lcs(int **k,char p[],int i,int j)
{
if(i==0||j==0)
return ;
if(k[i][j]==1)
{
print_lcs(k,p,i-1,j-1);//通過遞歸的方法按照輸入的從頭到尾的順序輸出LCS
cout<<p[i-1];
}
else if(k[i][j]==2)
print_lcs(k,p,i-1,j);
else
print_lcs(k,p,i,j-1);
}

2. 誰給個求最長公共子序列的演算法

首先告訴你個網路賬號叫pyx1997的人。他教會了我，現在讓我來教會你。
我們來看一組數據：
40 100 50 60 70
好，讓我們手動計算一下：
如果我們純貪心的話：高個i變數直接從頭到尾循環：到i=2時，就求得maxlen=2。i=5，maxlen被更新為3。但是我們看得出：最長不降子序列為40 50 60 70，maxlen=4。
為什麼，為什麼貪心會導致如此結果？那就是因為貪心童鞋的生理缺陷：目光短淺！
好了，讓我們在重新審題。
此時因為我們的最長不降子序列同時要求「最長」和「不降」這兩個方面，又因為我們的眼光要放長遠，所以我們選擇了用一個數組來記錄以當前為起點的最長不降子序列。醬紫的話，我們就把這個大問題分成來若干個小問題。又因為如果我們順退的話，我們不能確定到底是怎麼樣才算最長，前面的長度總是依賴於後面的長度。所以我們選擇倒推。
a:原始數據的存放數組。
f:狀態數組，即為以i(1<=i<=n)為起點的最長不降子序列的長度。不用設初值。
由於我不知道LZ使用的是什麼語言，所以這里給出偽代碼：
for i←n downto 1 //DP的次數
[maxlen←0 //將maxlen置空
for j←n downto i+1 //二重循環：比較i後的已知的最長不降子序列的長度。
if (f[j]>maxlen)&(a[i]>=a[j]) then maxlen←f[j] //求出最大值
f[i]←maxlen+1] //將最大值+1放入f[i]
然後，我們再將F數組掃描一遍，取最大值，即為答案。
如果要求序列的話，可以另開一個存放下一個值的數組next，然後再循環的最後加上一句next[i]←j
演算法描述完畢。具體的細節請自行調試。本人打的很辛苦，望lz給分。

3. 最長公共子序列演算法

可以用後綴數組搞。
可以看下這個
http://www.cnblogs.com/looker_acm/archive/2010/07/18/1780176.html

4. 最長 公共子序列問題（演算法分析 C++）

#include <iostream>
#include <string>
using namespace std;
//主函數
int main()
{
int m,n;
char *x,*y;
int **b,**c;
void LCSLength(int m,int n,char *y,char *x,int **c,int **b);
void LCS(int i,int j,char *x,int**b);

cout<<"請輸入兩個序列的長度："<<endl;
cin>>m>>n;
x=new char[m];
y=new char[n];
cout<<"請輸入兩個序列："<<endl;
cin>>x>>y;
b=new int *[m + 1]; // 注意這里，原式沒有+1
for (int i=0;i<=m;i++)
b[i]=new int[n + 1]; // 注意這里，原式沒有+1
c=new int *[m + 1];
for (int j=0;j<=m;j++)
c[j]=new int[n + 1]; // 注意這里，原式沒有+1
LCSLength(m,n,x,y,c,b);
cout<<"最長公共子序列的元素個數為"<<c[m][n]<<endl;
cout<<"該序列為:";
LCS(m,n,x,b); //注意後面的內容是清理，暫時先跳過去，你先搞定主程序先
/* delete []x;
delete []y;
for(int k=0;k<=m;k++)
delete []b[k];
delete []b;
for(int h=0;h<=m;h++)
delete []c[h];
delete []c;
*/
return 0;
}
//計算最優值
void LCSLength(int m,int n,char *y,char *x,int **c,int **b)
{
int i,j;
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}
else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}
else {c[i][j]=c[i][j-1];b[i][j]=3;}
}
}
//構造最長公共子序列
void LCS(int i,int j,char *x,int**b)
{
if(i==0||j==0)return;
if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}
else if(b[i][j]==2)LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}

5. C語言求最長子序列

下面是你的代碼修改過後的結果，改過的地方都有注釋，另有測試樣例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最長子序列：9
4
-2 -3 8 -7
最長子序列：8
3
-2 -2 7
最長子序列：7
2
-1 5
最長子序列：5
1
-2
最長子序列：0

Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.

*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在這里再加一個判斷條件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是負數的話，結果應該是0，即一個都不選
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最長子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}

6. O(nlogn)最長遞增子序列演算法,如何輸出所求子序列

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;

vector<int> dp(nums.size(), INT_MAX);
vector<int> pos(nums.size(), INT_MAX);

for (int i = 0; i < nums.size(); i++){
pos[i] = lower_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();
*lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
}
int max_n = lower_bound(dp.begin(), dp.end(), INT_MAX) - dp.begin();

vector<int> res(max_n, -1);
int j = max_n - 1;
for (int i = nums.size() - 1; i >= 0; --i){
if (j < 0) break;
if (j == pos[i]){
res[j--] = nums[i];
}
}
for (auto x : res)
cout << x << " ";
cout << endl;
return max_n;
}
};

int main() {
Solution s;
vector<int> nums = {12,2, 34, 4, 5, 6, 7, 8, 9, 0};
cout << s.lengthOfLIS(nums) << endl;
return 0;
}

7. 最長子序列演算法的程序 要求用C語言!

有兩種演算法復雜度為O(n*logn)和O(n^2)

O(n^2)演算法分析如下： （a[1]...a[n] 存的都是輸入的數）
1、對於a[n]來說，由於它是最後一個數，所以當從a[n]開始查找時，只存在長度為1的不下降子序列；
2、若從a[n-1]開始查找，則存在下面的兩種可能性：
（1）若a[n-1] < a[n] 則存在長度為2的不下降子序列 a[n-1],a[n].
（2）若a[n-1] > a[n] 則存在長度為1的不下降子序列 a[n-1]或者a[n]。
3、一般若從a[t]開始，此時最長不下降子序列應該是按下列方法求出的：
在a[t+1],a[t+2],...a[n]中，找出一個比a[t]大的且最長的不下降子序列，作為它的後繼。
4、為演算法上的需要，定義一個數組：
d:array [1..n,1..3] of integer;
d[t,1]表示a[t]
d[t,2]表示從i位置到達n的最長不下降子序列的長度
d[t,3]表示從i位置開始最長不下降子序列的下一個位置
最長不下降子序列的O(n*logn)演算法分析如下：
先回顧經典的O(n^2)的動態規劃演算法，設A[t]表示序列中的第t個數，F[t]表示從1到t這一段中以t結尾的最長上升子序列的長度，初始時設F[t] = 0(t = 1, 2, ..., len(A))。則有動態規劃方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
現在，我們仔細考慮計算F[t]時的情況。假設有兩個元素A[x]和A[y]，滿足
(1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y]
此時，選擇F[x]和選擇F[y]都可以得到同樣的F[t]值，那麼，在最長上升子序列的這個位置中，應該選擇A[x]還是應該選擇A[y]呢？
很明顯，選擇A[x]比選擇A[y]要好。因為由於條件(2)，在A[x+1] ... A[t-1]這一段中，如果存在A[z]，A[x] < A[z] < a[y]，則與選擇A[y]相比，將會得到更長的上升子序列。
再根據條件(3)，我們會得到一個啟示：根據F[]的值進行分類。對於F[]的每一個取值k，我們只需要保留滿足F[t] = k的所有A[t]中的最小值。設D[k]記錄這個值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的兩個特點：
(1) D[k]的值是在整個計算過程中是單調不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我們可以得到另外一種計算最長上升子序列長度的方法。設當前已經求出的最長上升子序列長度為len。先判斷A[t]與D[len]。若A [t] > D[len]，則將A[t]接在D[len]後將得到一個更長的上升子序列，len = len + 1， D[len] = A[t]；否則，在D[1]..D[len]中，找到最大的j，滿足D[j] < A[t]。令k = j + 1，則有D[j] < A[t] <= D[k]，將A[t]接在D[j]後將得到一個更長的上升子序列，同時更新D[k] = A[t]。最後，len即為所要求的最長上升子序列的長度。
在上述演算法中，若使用樸素的順序查找在D[1]..D[len]查找，由於共有O(n)個元素需要計算，每次計算時的復雜度是O(n)，則整個演算法的時間復雜度為O(n^2)，與原來的演算法相比沒有任何進步。但是由於D[]的特點(2)，我們在D[]中查找時，可以使用二分查找高效地完成，則整個演算法的時間復雜度下降為O(nlogn)，有了非常顯著的提高。需要注意的是，D[]在演算法結束後記錄的並不是一個符合題意的最長上升子序列！
這個演算法還可以擴展到整個最長子序列系列問題，整個演算法的難點在於二分查找的設計，需要非常小心注意。

8. 最長上升子序列

最長上升子序列問題是各類信息學競賽中的常見題型，也常常用來做介紹動態規劃演算法的引例，筆者接下來將會對POJ上出現過的這類題目做一個總結，並介紹解決LIS問題的兩個常用
演算法(n^2)和(nlogn).
問題描述:給出一個序列a1,a2,a3,a4,a5,a6,a7....an,求它的一個子序列（設為s1,s2,...sn），使得這個子序列滿足這樣的性質，s1<s2<s3<...<sn並且這個子序列的長度最長。輸出這個最長的長度。（為了簡化該類問題，我們將諸如最長下降子序列及最長不上升子序列等問題都看成同一個問題，其實仔細思考就會發現，這其實只是<符號定義上的問題，並不影響問題的實質）
例如有一個序列:1 7 3 5 9 4 8,它的最長上升子序列就是 1 3 4 8 長度為4.

演算法1(n^2):我們依次遍歷整個序列，每一次求出從第一個數到當前這個數的最長上升子序列，直至遍歷到最後一個數字為止，然後再取dp數組里最大的那個即為整個序列的最長上升子序列。我們用dp[i]來存放序列1-i的最長上升子序列的長度，那麼dp[i]=max(dp[j])+1,(j∈[1, i-1]); 顯然dp[1]=1,我們從i=2開始遍歷後面的元素即可。

9. c++中怎麼求數組中最長的遞增序列

例如數組 data[]={-9,0,-3,-5,-1,-2}
最後求得最長遞增子序列的長度為 3 （-9，-3，-1），當然還有好幾種同種長度的遞增子序列的組合
核心演算法：
C++表示演算法如下：
// 求數組中最長遞增子序列
int Array::Max_Length_GoUp_stack(int *data,unsigned int const length)
{
// 異常輸入，ITJOB
if(data == NULL || length == 0)
{
cout<<"輸入異常 Max_Length_GoUp"<<endl; return="" 0;="" }="" 正常輸入="" else="" {="" 核心演算法，用工具棧去解決問題="" stack * S = new stack;
S->push(0);
unsigned int now = 0;
unsigned int result = 1;
while(S->empty() == false)
{
// 可以進棧
now ++;
if(now < length)
{
while(now < length)
{
if(data[now] > data[S->top()])
{
S->push(now);
}
now++;
}
// 更新結果
if(S->size() > result)
result = S->size();
}
// 出棧操作
else{
now = S->top();
S->pop();
}
}
// 返回結果
return result;
}
}

10. 求最長單調序列C++演算法

你這個例子不對吧？300 250 275 252 200 138 245，輸出應該是
275 252 200 138吧？我編的演算法（連續兩個相等的不算增也不算減）：
#include<iostream>
using namespace std;
int main()
{
int num[200],n,len,maxlen,begin,end,mxbegin,mxend,i,increase;
cout<<"輸入序列的總長度："<<endl;
cin>>n;
cout<<"輸入各個數："<<endl;
for(i=0;i<n;i++)
cin>>num[i];
begin=end=len=maxlen=mxbegin=mxend=0;
if(num[1]>num[0])
increase=1;
else
increase=0;
for(i=1;i<n;i++)
{
if(num[i]>num[i-1] && increase==1)
end=i;
else if(num[i]<num[i-1] && increase==0)
end=i;
else if(num[i]>num[i-1] && increase==0)
{
len=end-begin+1;
if(len>maxlen)
{
maxlen=len;
mxbegin=begin;
mxend=end;
}
begin=i-1;
end=i;
increase=1;
}
else if(num[i]<num[i-1] && increase==1)
{
len=end-begin+1;
if(len>maxlen)
{
maxlen=len;
mxbegin=begin;
mxend=end;
}
begin=i-1;
end=i;
increase=0;
}
else
{
len=end-begin+1;
if(len>maxlen)
{
maxlen=len;
mxbegin=begin;
mxend=end;
}
begin=end=i;
increase=0;
}
}
if(end==n-1 && end-begin+1>maxlen)
{
maxlen=end-begin+1;
mxbegin=begin;
mxend=end;
}
for(i=mxbegin;i<=mxend;i++)
cout<<num[i]<<" ";
cout<<endl;
return 0;
}