Cách tốt hơn để giải quyết bài này có độ phức tạp O(N), dựa vào tính chất dãy số dương.
Xét dãy con liên tiếp
kết thúc tại j, gọi i là vị trí
xa nhất về bên trái sao cho đảm bảo điều kiện tổng từ i đến j <=M. Giả sử đã tìm đc một cặp (i,j) nào đó. Ta nhận xét: "Với mỗi cặp (x,y), nếu (y>j) thì chắc chắn (x>=i)".
Vd ta xét vị trí j, ta tìm đc i tương ứng của nó. Vì i là vị trí xa nhất sao cho tổng [i,j]<=M nên ta chắc chắn tổng từ [i-1,j]>M. Vậy với (j+1) ta chỉ cần kiểm tra điều kiện tổng từ i đến (j+1) <=M, nếu thỏa thì tiếp tục tăng j, nếu ko thì tăng i lên đến khi thỏa.
Code:
getmax:=low(longint); {gán biến getmax bằng giá trị nhỏ nhất của kiểu longint}
i:=1;
tong:=0;
for j:=1 to n do
begin
tong:=tong+a[j];
while (tong>M) do begin tong:=tong-a[i]; i:=i+1; end;
if (j - i + 1 > getmax) then getmax:=j - i + 1;
end;
writeln(getmax);