отобразить самую длинную возрастающую подпоследовательность
#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;
}
Это была программа, которую я сделал для нахождения самой длинной возрастающей подпоследовательности. Я получаю длину подпоследовательности правильно, но я не получаю последовательность правильно. Я думаю, что может быть проблема с последним циклом for, который содержит переменную k, но я не могу понять это. Помогите мне, пожалуйста.
Решение
На самом деле вы написали правильную последовательность, но в обратном порядке и пропустили первый (последний) элемент
Вы можете изменить последний, чтобы включить первый элемент
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 << ' ';
}
Другие решения
Других решений пока нет …