Bài 3. Dãy số (HSG THPT TP. Cần Thơ 2026)
Xem dạng PDFCho một dãy số ~A~ gồm ~n~ phần tử số nguyên có dạng ~a_1, a_2, \ldots, a_n~. Gọi ~W~ là tổng giá trị của ~n - 1~ phần tử được chọn ra trong ~A~. Mỗi lần chọn một phần tử trong hai phần tử đầu tiên và thực hiện theo quy tắc sau:
• Nếu chọn ~a_1~ thì ~W = W + a_1~, sau đó lấy ~a_1~ ra khỏi dãy thì phần tử ~a_2~ lúc này là ~a_1~, phần tử ~a_3~ là ~a_2, \ldots~
• Ngược lại, nếu chọn ~a_2~ thì ~W = W - a_2~, sau đó lấy ~a_2~ ra khỏi dãy thì phần tử ~a_3~ lúc này là ~a_2, \ldots~
Yêu cầu: Hãy lặp lại quy tắc trên một cách tối ưu, xác định giá trị ~W~ lớn nhất khi chọn ra đúng ~n - 1~ phần tử.
Dữ liệu vào
Gồm hai dòng:
- Dòng đầu tiên ghi số ~n (2 \le n \le 10^5)~.
- Dòng tiếp theo ghi các số ~a_i (|a_i| \le 10^4)~, mỗi số cách nhau bởi một dấu cách.
Kết quả
Một số nguyên là kết quả tìm được.
Ví dụ
Input 1
4
1 2 -3 2
Output 1
6
Thứ tự chọn tối ưu như sau: ~W = 1 - (-3) + 2 = 6~.
Ràng buộc
- 30% số test tương ứng với số điểm có ~a_i > 0~.
- 20% số test tương ứng với số điểm có ~n \le 15~.
- 50% số test còn lại không ràng buộc gì thêm.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).