顯示最長的遞增子序列

#include<iostream> 
using namespace std; 
int main() 
{ 
    int a[]={0,8,4,12,2,10,6,1,9,5,13,3,11,7}; 
    int b[50],i,j,n,ls[50]; 
    n=sizeof(a)/sizeof(a[0]); 
    int maxlen=0,end=-1; 
    b[0]=-1; 
    for(i=0;i<n;i++) 
    { 
     ls[i]=1; 
     for(j=0;j<i;j++) 
     { 
      if(a[i]>a[j] && ls[i]<ls[j]+1) 
      { 
       ls[i]=ls[j]+1; 
       b[i]=j; 
      } 
     } 
     if(ls[i]>maxlen) 
     { 
      end=i; 
      maxlen=ls[i]; 
     } 
    } 

    cout<<maxlen<<endl; 
    for(int k=end;b[k]!=-1;k=b[k]) 
    { 
     cout<<a[k]; 
    } 
      return 0; 
}

這是我爲了找到最長的遞增子序列而完成的程序。我正確地獲得了子序列的長度，但我沒有正確地獲得序列。我認爲可能有一個問題，最後一個循環包含變量k，但我無法弄清楚。請幫幫我。顯示最長的遞增子序列

來源

2013-06-28 Info Seeker

格式化您的代碼 – aaronman

我剛剛運行您的代碼，它打印5的最長增加序列的長度。我沒有看到長度超過2的增加的子序列...我認爲你需要仔細檢查你的邏輯尋找最長的序列。 – jlars62

@ jlars62 - 「[最長的遞增子序列]（http://en.wikipedia.org/wiki/Longest_increasing_subsequence）」問題通常不要求子集是連續的。 –

其實你寫的正確順序，但以相反的順序，並跳過第一個（最後一個）元素

您可以更改持續到包括第一元素

vector<int> v; 
for(int k=end;k!=-1;k=b[k]) 
{ 
    cout << a[k] << ' '; 
}

您可能需要存儲元素像std::vector扭轉它得到正確的順序

vector<int> v; 
for(int k=end;k!=-1;k=b[k]) 
{ 
    v.push_back(a[k]); 
} 
reverse(v.begin(), v.end()); 
for(int x: v) { 
    cout << x << ' '; 
}

http://ideone.com/URPACA

來源

2013-06-28 21:37:10 RiaD

顯示最長的遞增子序列

回答

相關問題