Bài toán dãy con tăng dần dài nhất (Sưu tầm)

Bài viết sau được mình sưu tầm trên trang web: csharpviet.freevnn.com

với mục đích tiện tra cứu và tìm đọc lại mỗi khi cần (Và có sửa đổi một chút).

Cảm ơn tác giả vì bài viết rất hữu ích

------------------------------------------------------------------------------------------------------------------------------------

Nội dung:

Bài toán:
Cho dãy số A gồm n phần tử: a[1], a[2],..., a[n].
Dãy B được gọi là dãy con của A nếu B được tạo ra bằng cách xóa một số phần tử của A. Hãy tìm dãy con tăng dần dài nhất của A.

VD:
Input: 1 3 2 5 7 6 4 2 5
Output: 1 2 2 5

Có rất nhiều cách để giải bài toán này.
Ở đây ta sử dụng phương pháp quy hoạch động để giải quyết.
PP này tiết kiệm chi phí cho bài toán và chạy rất nhanh.

Công thức quy hoach động:

Nhận xét:

+Để tìm dãy con dài nhất trong đoạn từ a[0]->a[n], ta có thể tìm một dãy con B nào đó trong đoạn
a[0]->a[i] (i<n) có phần tử cuối là a[j] (j <= i) . Như vậy ta sẽ tìm chiều dài dãy con tăng dần dài nhất trong mỗi dãy con B như vậy xác định tại mỗi vị trí i. Chiều dài tại vị trí thứ i được xác định bởi chiều dài dãy con đứng trước đó.

Ví dụ:
Vị trí : i =0: L[i] = 1;
i = 1: L[i] = 2;
i = 2: L[i] = 2;
.....
i = 9: L[i] = 4;

Như vậy:

Ta đã chuyển bài toán ban đầu về bài toán có cùng kiểu nhưng kích thước nhỏ hơn.

Mục tiêu của bài toán là độ dài của dãy con tăng dần dài nhất tại mỗi vị trí i. Ta gọi: L[i] là độ dài của dãy con tăng dần dài nhất trong đoạn từ a[0]->a[i];

Nếu i =1: L[i] = 1;
ngược lại: L[i] = L[j] + 1 với 0<=j<=i nếu a[i]>= a[j] và L[j] la max

Đây chính là công thức quy hoạch động của bài toán.

Vì chúng ta chỉ lưu trữ độ dài lớn nhất của dãy tại mỗi vị trí của dãy nên mảng phương án sẽ là mảng một chiều có n phần tử.

Truy vết:

1) Ta duyệt bảng phương án, tìm phần tử lớn nhất.
2)Duyệt từ phần tử max về đầu bảng phương án, giảm dần max, ta sẽ lấy giá trị các phần tử a[i]
mà L[i] = max.
3)Chèn phần tử a[i] vào dãy con C. Sau khi duyệt xong, C chính là dãy con cần tìm.

//DayConTangDanDaiNhat.cpp
/*:
 Chuong trinh sau lay y tuong cua nguon code tu csharpviet.freevnn.com
 Chuong trinh goc duoc viet theo C#, minh chuyen lai qua C++
*/

#include<iostream>
#include<stdlib.h>
#define MAX 100
using namespace std;

int arr[MAX]; //Day so ban dau
int L[MAX]; //Bang phuong an
int n; //Do dai cua day

//Tim bang phuong an
void BangPhuongAn()
{
 int i,j;
 for(i = 0;i<n;++i)
 {
  L[i] = 1;
  //Tim phan tu a[j]<=a[i] sao cho do dai day con a[0]...a[j] la lon nhat
  for(j=0;j<i;++j)
  {
   if(arr[j]<=arr[i] && L[i]<L[j]+1)
   {
    L[i] = L[j]+1;
   }
  }
 }
}

//Ham truy vet day con thoa man yeu cau
void Trace()
{
 //Tim chi so phan tu lon nhat trong bang phuong an
 int maxi = 0;
 for(int i =1;i<n;++i)
 {
  if(L[i] > L[maxi])maxi = i;
 }
 
 //Duyet quay lui va giam dan max lay phan tu a[i] co l[i] la max
 int max = L[maxi];
 int s[max+1], t = max;
 while(maxi>=0 && max>0)
 {
  if(L[maxi] == max)
  {
   s[max] = arr[maxi];
   --max;
  }
  --maxi;
 }
 for(int i =  1;i<=t;++i)cout<<s[i]<<" ";
 cout<<endl;
}

int main()
{
 cout<<"Nhap so phan tu cua day: "; cin>>n;
 cout<<endl<<"Nhap day so:"<<endl;
 for(int i =0;i<n;++i)cin>>arr[i];
 cout<<endl<<"Day con tang dan dai nhat: "<<endl;
 BangPhuongAn();
 Trace();
 system("pause");
 return 0;

}