#1080. SPSEQ - Chia dãy

Cho dãy số . Tìm cách chia dãy thành đoạn liên tiếp sao cho tổng các số trong đoạn lớn nhất là nhỏ nhất. Đoạn lớn nhất của một cách chia là đoạn có tổng lớn nhất trong các đoạn được chia.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên .
• Dòng thứ hai chứa số nguyên .

Dữ liệu ra:

• Một số nguyên duy nhất là tổng các số trong đoạn lớn nhất theo cách chia tìm được.

Ví dụ:

Dữ liệu vào:

5 2
8 2 1 5 6

Dữ liệu ra:

8

Dữ liệu vào:

10 3
1 2 3 4 5 6 7 8 9 10

Dữ liệu ra:

17

Giải thích:

• Trong test : Cách chia tối ưu là

Giới hạn:

• số test có ;
• số test có ;
• số test còn lại có .