Đoạn con 3

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Cho một dãy gồm $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Yêu cầu: Hãy chọn ra đúng $3$ đoạn con liên tiếp không giao nhau (không có phần tử chung) của dãy sao cho tổng các phần tử trong $3$ đoạn con đó là lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $n$ ( $3 \leq n \leq 10^{5}$ ).
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ ( $| a_{i} | \leq 10^{9}$ ).

Dữ liệu ra

Ghi ra một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Ví dụ

Input	Output	Giải thích
7 1 -2 3 4 -1 5 -3	11	Chọn $3$ đoạn con: $[1]$ , $[3, 4]$ và $[5]$ . Tổng $= 1 + (3 + 4) + 5 = 13$ . Hoặc chọn $[1]$ , $[3, 4, - 1, 5]$ không được vì chỉ là $2$ đoạn. Một cách hợp lệ: $[1]$ , $[3, 4]$ , $[5]$ cho tổng $= 13$ .
5 -1 -2 -3 -4 -5	-6	Buộc phải chọn $3$ đoạn, cách tốt nhất là chọn $3$ phần tử lớn nhất: $[- 1]$ , $[- 2]$ , $[- 3]$ . Tổng $= - 1 + (- 2) + (- 3) = - 6$ .

Bình luận

Không có bình luận tại thời điểm này.