Bài toán này có 1 cách làm đơn giản là dùng 2 biến chạy i,j với j>=i. Với mỗi cặp i,j ta kiểm tra xem đoạn con liên tiếp từ phần tử thứ i đến phần tử thứ j có thỏa điều kiện <=M hay ko, nếu thỏa thì tính độ dài và cập nhật để thu đc độ dài đoạn con dài nhất.
Code:
kq:=0; {biến kq lưu độ dài lớn nhất tìm được, ban đầu gán kq=0}
for i:=1 to n-1 do
for j:=i to n do
begin
tong:=0;
for k:=i to j do tong:=tong+a[k]; {tính tổng các số từ i đến j}
if (tong<=m) and (j+1-i>kq) then kq=j+1-i; (*)
end;
writeln(kq);
trong đó phần được đánh dấu (*) diễn tả: "kiểm tra 2 điều kiện: tổng của dãy số phải <=m và chiều dài đoạn từ i đến j phải lớn hơn chiều dài lớn nhất tìm được trước đó"
Nhưng với cách làm này rõ ràng không quan trọng a[i] âm hay dương, nhưng đề bài lại cho dãy số dương, nên ta có một cách làm khác có thể tăng tốc hơn rất nhiều. Cách này sẽ đc post sau
