Dãy số ai, ai+1, …, aj với 1 ≤ i ≤ j ≤ n được gọi là dãy con của dãy số đã cho và khi đó, j-i+1 được gọi là độ dài, còn ai+ai+1…+aj được gọi là trọng lượng của dãy con này.

Yêu cầu: cho số nguyên p, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn p hãy tìm dãy con có độ dài lớn nhất.

9. Dãy con đơn điệu dài nhất 1. Mô hình Cho dãy a1,a2,..an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. Đặc trưng: i) Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử aitrong dãy, khác với các bài toán của mô hình 4(đặc trưng là bài toán đổi tiền), các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị. ii) Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau. 2. Công thức QHĐ Hàm mục tiêu : f = độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính L(i) như sau: • L(1) = 1. (Hiển nhiên) • L(i) = max(1, L(j)+1 với mọi phần tử j: 0

Trong bài viết này chúng ta sẽ cùng làm bài toán là tìm dãy con có tổng trọng số lớn nhất trong mảng.

Cụ thể bài toán có thể phát biểu như sau: Viết chương trình tìm dãy con có tổng trọng số lớn nhất trong mảng, tính tổng trọng số và in ra dãy con đó. Sử dụng 3 phương pháp là duyệt qua tất cả phần tử mảng, quy hoạch động và chia để trị.

Ví dụ: -5 0 -4 1 5 -2 5

Dãy con có tổng trọng số lớn nhất là: 5 -2 5 1 và có tổng trọng số là 9.

Giải bằng phương pháp duyệt qua tất cả phần tử

Đối với bài toán này thì phương pháp này là đơn giản nhất mà hầu hết ai cũng có thể nghĩ ra và làm được, tuy nhiên thuật toán lại không hề tối ưu và chạy rất tốn time nếu mảng từ vài trăm ngìn phần tử.

Ý tưởng là ta sẽ duyệt 3 vòng lặp để lấy hết từng dãy con của mảng và tính tính tổng. Duyệt đến dãy con nào có tổng trọng số lớn hơn thì ta sẽ gắn bằng maxx và lưu dãy con vào một mảng temp, thực hiện lặp cho đến khi hết tất cả dãy con lúc đó maxx chính là tổng trọng số lớn nhất, temp là dãy con đó.

• Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
• Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
• Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%

Ta viết chương trình như sau:

include

using namespace std; int main() { int a[]={-5,0,-4,1,5,-2,5}; //mảng a int n = sizeof(a)/4; //Số phần tử mảng a int maxsum = 0; //tổng dãy con lớn nhất int sum = 0; //sum để tính tổng từng dãy con int vtd = 0, vtc = n-1; //Lưu vị trí đầu và cuối để lát nữa lấy ra dãy con đó(hiểu là mảng temp) //Vòng lặp i j để lấy từng dãy con có trong mảng có thể sảy ra //Ví dụ dãy con có thể là từ vt1 tới vt5, vt3 tới vt4, vt2 tới vt4....v.v for (int i = 0; i < n; i++) {

for(int j=i;j

temp+a[i]<0?temp=0:temp+=a[i];

if(temp > maxsum){
  maxsum = temp;vt=i; //Gắn lại maxsum và vị trí kết thúc của dãy con
}

 int a[]={-5,0,-4,1,5,-2,5};

 int sum = QHD(a,n); //Gọi  uy hoạch động với dãy a

 cout<

 while(sum>0)
 {
   cout<