Chọn phần thưởng
Xeng là người đạt giải đặc biệt trong một kỳ thi năng khiếu do trường tổ chức, Xeng được
chọn các phần thưởng cho mình. Các phần thưởng được xếp thành một dãy gồm N phần được
đánh thứ tự từ 1 đến N, phần thưởng thứ i có giá trị ai. Xeng được phép chọn các phần thưởng
của mình theo nguyên tắc không chọn ba phần thường liên tiếp bất kỳ.
Yêu cầu: Hãy giúp Xeng tìm ra cách chọn sau cho tổng giá trị phần thưởng là lớn nhất?
Dữ liệu vào: File reward.inp gồm 2 dòng
+ Dòng 1: Ghi số N (0<N<10^5)
+ Dòng 2: Ghi N số a1, a2,, AN (0<ai<10^9)
Dữ liệu ra: Ghi ra file reward.out gồm duy nhất một số là giá trị các phần thường lớn nhất mà
Xeng có thể nhận được.
Ví dụ:
Reward.inp Reward.out
5
6 9 1 3 5
23
Giới hạn:
+ 50% số test ứng với N<100
+ 50% số test ứng với N<10^5