Cho một dãy số nguyên dương có độ dài . Cần chia dãy này thành đoạn liên tiếp sao cho giá trị lớn nhất của tổng các đoạn con là nhỏ nhất có thể.
Ví dụ, chia dãy thành đoạn:
- Nếu chia thành , tổng các đoạn lần lượt là . Giá trị lớn nhất là .
- Nếu chia thành , tổng các đoạn lần lượt là . Giá trị lớn nhất là .
Dù chia thế nào thì giá trị lớn nhất cũng không thể nhỏ hơn .
Vì vậy, với dãy chia thành đoạn, giá trị lớn nhất của tổng các đoạn nhỏ nhất là .
Dữ liệu:
- Dòng 1 chứa hai số nguyên dương và .
- Dòng 2 chứa số nguyên không âm cách nhau bởi dấu cách.
Kết quả:
- Một số nguyên dương duy nhất, là giá trị lớn nhất của tổng các đoạn sau khi đã tối thiểu hóa.
Ví dụ:
Dữ liệu:
Kết quả:
Giới hạn:
- Với dữ liệu: .
- Với dữ liệu: .
- Với dữ liệu: , , tổng các không vượt quá .
