[duyhung123abc]

Nguyên văn bởi duyhung123abc

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.

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

Với cùng cách tiếp cận trên, có thể giảm xuống còn 2 vòng lặp lồng nhau chứ không cần đến 3 vòng lặp. Nhận xét là ta xét cặp (i,j-1) trước và ngay sau đó xét tới cặp (i,j), nên ta có thể tính tổng cặp (i,j) dựa và tổng cặp (i,j-1). Gọi x là tổng của (i,j-1) thì tổng của (i,j) là (x + a[j]). Ta chuyển độ phức tạp từ O(N^3) xuống còn O(N^2)