#1011. SUMSEQ - Tổng lớn nhất

Cho một dãy số nguyên gồm phần tử . Gọi là giá trị của dãy con liên tiếp có tổng lớn nhất của dãy . Ví dụ: .

Yêu cầu: Cho một số nguyên , hãy tìm cách tăng mỗi phần tử trong tối đa một dãy con liên tiếp của dãy lên lần sao cho lớn nhất có thể.

Dữ liệu vào:

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

Dữ liệu ra:

• In ra trên một dòng giá trị lớn nhất của

Ví dụ:

Dữ liệu vào:

5 2
5 -1 2 -3 2

Dữ liệu ra:

12

Giải thích:

• Ta nhân với , tức là . Khi đó thì

Giới hạn:

• số test có
• số test khác có
• số test còn lại có