#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
的最后一个 for 循环可能有问题,但我无法弄清楚。请帮助我。
最佳答案
实际上你写的顺序是正确的,但顺序相反并跳过了第一个(最后一个)元素
您可以更改最后一个以包含第一个元素
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 << ' ';
}
关于c++ - 显示最长的递增子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17373856/