mảng con dài nhất

[G.Perelman]

cho 1 mảng A,yêu cầu tìm mảng con dài nhất
ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.

[Forlorn_hope]

lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử

Sao không dùng qui hoạt động.
Mà bạn post bài lên là để thảo luận giải thuật hả?

[rox_rook]

cho 1 mảng A,yêu cầu tìm mảng con dài nhất
ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.

Vẫn chưa thấy yêu cầu bài toán, tính chất của dãy dài nhất là gì ?

[nthung]

cho 1 mảng A,yêu cầu tìm mảng con dài nhất
ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.

Quy hoạch động được không bạn

 #include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#define duongvocung 3200
#define amvocung -3200
int n,i,j,l[100],a[100];
static int k,max,jmax;
// k danh dau vi tri phan tu bat dau cua day con tang lon nhat
// n la do dai cua day
//l la mang chua do dai lon nhat cua tung phan tu khi tinh tu cuoi day
// a la mang chua cac phan tu
void nhap(){
clrscr();
cout<<"Dynamic prigramming\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"\n";
cout<<"Tim day con tang dai nhat cua mot day\n\n\n\n\n\nSo phan tu cua day la:";
cin>>n;
cout<<"\n\n\n\n\n";
cout<<"Nhap cac phan tu cua day:\n";
for(i=1;i<=n;i++)
cin>>a[i];
}

//////////////////////////////////////////
/// day la ham tim do dai day con tang lon nhat
void tinh_f()
{
a[n+1]=duongvocung;//a[n+1]=3200 phan tu duong vo cung
l[n+1]=1;//do dai phan tu duong vo cung la 1
a[0]=amvocung;//a[0]=-3200 phan tu am vo cung
for(i=n;i>=0;i--)
{
jmax=n+1;
for(j=n+1;j>=i+1;j--)
if(a[i]<a[j]&&l[j]>=l[jmax])
{
jmax=j;
l[i]=l[j]+1;

}
}
}
///////////////////////////////////////////////////////////////////////
// ham xemday()in ra day ban da nhap

void xemday(){
for(i=1;i<=n;i++)
cout<<" "<<a[i];
}
////////////////////////////////////////////////
//ham tim_max() in ra do dai day con tang lon nhat
void tim_max(){
int t=0;
max=l[1];
for(i=1;i<=n;i++)
if(max<=l[i]){
max=l[i];
k=i;
}
for(i=k;i<=n;i++)

if(max-l[i]==t&&a[i]>=a[k])
{
cout<<" "<<a[i];
t++;
}

}
///////////////////////////////////////////////////////////////////
void main(){
nhap();
cout<<"day ban da nhap:\n";
xemday();
cout<<"\n";
tinh_f();
cout<<"day ket qua la:\n";
tim_max();
getch();
}

[G.Perelman]

to rox_rook :thành thật xin lỗi nha,tên bài viết lẽ ra phải là "dãy con tăng dài nhất",giờ thì chắc bạn đã hiểu đề bài.
To nthung giải thuật của bạn là đúng,song rất tiếc mình chưa biết gì về C++ mà chỉ rành về C ,nhưng nói chung tư tưởng đúng thì phần cài đặt không vấn đề gì.
Sau đây là giải thuật của mình :
gọi n là số phần tử của mảng ,khi đó mình quy về đồ thị n đỉnh như vậy trọng số trên 1 cạnh (i,j) sẽ là c[i][j]=1,nếu a[i]<=a[j] && i<j.
else c[i][j]=0;
sử dụng thuật toán Floyd để tìm đường đi dài nhất giữa mọi cặp đỉnh --> kết quả.

[xuanhung_cntt]

hay lắm tanglung

[dangtin]

Em thấy bài này cần gì phải quy hoạch động với đồ thị ạ, mình chỉ cần cho duyệt cả mảng rồi so sánh lần lượt các phần tử cạnh nhau a[i-1] và a[i], nếu a[i-1]<a[i] thì vẫn ở trong mảng con, nếu a[i-1]>a[i] thì sẽ hết mảng con, ta lại so sánh độ dài với mảng con tăng dài nhất đã biết, rồi tiếp tục chạy. Thế này đơn giản hơn còn gì ạ? Với lại Floyd của anh G.Perelman có thời gian O(n^3) còn quy hoạch động hình như là O(nlgn) em không nhớ rõ lắm, còn cách duyệt tuần tự thì chỉ có O(n) thôi ạ.
Em mới học, có gì sai mọi người thông cảm