Reply: nhờ mọi nguoi giai giup bai quy hoach dong
Mình mới đọc lại đề thì thấy có chỗ chưa rõ: đoạn con tăng dần có cần liên tiếp hay không vậy bạn?
1) Nếu là đoạn con liên tiếp: bài này không khó, không cần tới qhđ. Chỉ cần 1 vòng lặp là đủ. Pseudo-code của nó đại loại như thế này:
Mã:
currentSum = maxSum := a[1];
index := 1;
for i := 2 to n do
begin
if (a[i - 1] < a[i]) then
currentSum := currentSum + a[i]
else
currentSum := a[i];
if (currentSum > maxSum) then
begin
maxSum = currentSum;
index := i;
end;
end;
Đây chỉ là pseudo-code, có thể còn lỗi. Thuật toán của mình là vừa đi vừa tính tổng khi nào dãy còn tăng, lưu vào 'currentSum'. Nếu dãy không còn tăng nữa thì reset lại 'currentSum'. Mỗi lần vậy cần so sánh 'currentSum' và 'maxSum'. Biến 'index' là lưu lại vị trí xảy ra tổng max. Sau khi hết vòng lặp rồi thì bạn duyệt ngược từ vị trí index cho tới khi dãy không còn giảm nữa để in ra dãy cần tìm. Thuật toán có độ phức tạp O
.
Ví dụ của bạn chính là trường hợp 1 này.
2) Nếu là đoạn con không liên tiếp: bài này mới cần quy hoạch động. Công thức quy hoạch động giống như post #2 của mình nhé, nhưng mình sửa lại lúc khởi tạo phải là
Đoạn code đại khái như thế này:
Mã:
- Khởi tạo F[i] = a[i] cho toàn bộ 1 <= i <= n.
- Khởi tạo track[i] = -1 cho toàn bộ 1 <= i <= n. // Mảng track này sẽ lưu lại chỉ số của phần tử đến từ trước nó.
- index := 1; // Lưu lại vị trí (chỉ số) của F max. Ban đầu giả sử tổng max ở vị trí 1.
for i := 2 to n do
begin
for j := 1 to i - 1 do
if (a[j] < a[i] and f[i] < a[i] + f[j]) then // tìm đc dãy con có tổng lớn hơn
begin
f[i] := a[i] + f[j];
track[i] := j; // trước khi đến i phải qua j.
end;
if (f[i] > f[index]) then // có tổng max mới
index := i; // tổng max mới ở vị trí i.
end;
Sau khi ra khỏi vòng loop, tổng max sẽ đc lưu ở 'f[index]'. Còn muốn in ra dãy con thì chúng ta phải duyệt ngược mảng 'track'. Kết quả sẽ như thế này, ví dụ sơ sơ:
Mã:
writeln(a[index]);
k := track[index];
while (k <> -1) do
begin
writeln(a[k]);
k := track[k];
end;
Độ phức tạp của thuật toán O(n^2). Nếu n tới 10000 thì chạy không nổi. Cái khó phải optimize chính là vòng lặp j (hiện tại là O
), khi đó phải dùng cấu trúc cây nhị phân để tìm max trong thời gian O(log n).
Ví dụ của bạn sẽ ra là 9, 8, 7, 6, 5, 4, 2, 1.
