Tìm dãy con tăng dài nhất (Ví dụ đơn giản trên C++)

#include <iostream>
#include <vector>
using namespace std;

// Input
#define MAX 1010

int a[MAX]={7, 9, 15, 3, 9, 10, 7, 5};
int n=8;

// Output
int f[MAX];
int pre[MAX];

void TinhF()
{
// Khởi tạo
for (int i=0; i<n; i++)
pre[i]=-1;

f[0]=1;
for (int i=1; i<n; i++)
{
f[i]=1;
for (int j=0; j<i; j++){
if (a[j] <= a[i]){
if (f[i] < f[j]+1)
{
f[i] = f[j]+1;
pre[i] = j;
}
}
}
}
}
vector<int> daycontang;
void TruyVet()
{
int gtmax=f[0];
int vitri = 0;

for (int i=1; i<n; i++)
if (gtmax < f[i])
{
gtmax = f[i];
vitri=i;
}

// Tim day con tang dai nhat
for (int i=vitri; i!=-1; i=pre[i])
daycontang.push_back(a[i]);
int len = daycontang.size();
for (int i=len-1; i>=0; i--)
cout << daycontang[i] << " ";
cout << endl << "Do dai: " << gtmax;
}

int main()
{
TinhF();
TruyVet();
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s