Cho một dãy X[1..n]. Tìm dãy con liên tiếp cạnh nhau của X có tổng lớn nhất.

Ban QT: Kể cũng vui thật.

Thử xem code này được không? Ở đây chỉ viết gợi ý, Khách viếng thăm hãy hoàn thiện thêm input, output nha. Tôi thì cố gắng thi lấy 5 điểm thôi, còn bài dạng này nhường các bạn giỏi, cũng viết gợi ý để các bạn làm cho nó tốt nha:

1. Mô hình
Cho dãy X₁, X₂,.. Xn. 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ử Xi trong dãy, 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 quy hoạch động 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ừ X₁ đến X_i và phần tử cuối cùng là X_i.
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 < j < i và X_j ≤ X_i).
Tính L(i) : phần tử đang được xét là Xi . Ta tìm đến phần tử Xj < Xi có L(j) lớn nhất. Khi đó nếu bổ sung Xi vào sau dãy con ...Xj ta sẽ được dãy con tăng dần dài nhất xét từ X₁...Xi.
A)

Dãy con có nhiều phần tử tăng nhất:

B)

Dãy con có tổng lớn nhất:

[You must be registered and logged in to see this link.].

max := x[1];
i_o := 1; j_o := 1;

FOR i := 1 TO n DO
          S := 0;
          FOR j := i TO n DO
                    S := S + a[j]; /* Tính tổng từ x[i] đến x[j] */
                    IF S > max THEN
                              max := S;
                              i_o := i; j_o := j;

Output a[i_o],..., a[j_o]; max;

Đúng như anh Admin nói những bài này giành cho những người khá và muốn kiếm điểm 10.
Bài toán anh Admin đưa ra khác hẳn bài này. Vả lại anh Admin viết giả mã sai rồi, không đúng. Ah nghiên cứu và viết lại nhé.
Giải thuật của anh Phương sai rồi. Ví dụ: 13 -15 2 3 4 7 8 0 -5. Anh dùng giải thuật của anh xem kết quả thế nào.

Ban QT: Down File Admin gửi link kèm bài viết trên, đã rõ hết rồi

Chú chưa thử bài của anh mà dám phán luôn là sai, bựa nhân quá.

Anh chạy tay cho chú xem thế nào nhé.

Max= 13;

i= 1
s= 0;
j= 1, s= 13
j= 2, s= -2
j= 3, s= 0
j= 4, s= 3
j= 5, s= 7
j= 6, s= 14, max= 14
j= 7, s= 22, max= 22
j= 8, s= 22
j= 9, s= 17


i= 2;
s= 0;
j= 2, s= -15
j= 3, s= -13
j= 4, s= -10
j= 5, s= -6
j= 6, s= 1
j= 7, s= 9
j= 8, s= 9
j= 9, s= 4


i= 3;
s= 0;
j= 3, s= 2
j= 4, s= 5
j= 5, s= 9
j= 6, s= 16
j= 7, s= 24, max= 24
j= 8, s= 24
j= 9, s= 19

tương tự cho i=4,5,6,7,8,9 nhé. Bởi vì nhìn qua cũng thấy là max=24 rồi, trong trường hợp này tương ứng với i=3, j=7, có nghĩa là tổng dãy a3, a4, a5, a6, a7 là lớn nhât.

Uh. Đúng rồi. Sorry a.Phương nhé. Em nhìn lướt qua, không nhìn kỹ. Cách của a cũng được. Bản chất là anh duyệt hết. Cách này được 0.5 điểm. Còn hơn là không làm được.

Để được 1 điểm bài này phải dùng quy hoạch động. Dựa vào tính chất của dãy.