VOI 09 Bài 1 - Trò chơi với băng số
Xem dạng PDF
Gửi bài giải
Điểm:
0,08 (OI)
Giới hạn thời gian:
0.6s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm ~n~ ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ ~i~ người ta ghi một số nguyên dương ~a_{i}~, ~i = 1, 2, \dots, n~. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô ~i_{1}, i_{2}, \dots, i_{k}~. Khi đó điểm số mà người chơi đạt được sẽ là:
- ~a_{i_1} - a_{i_2} + \dots + (-1)^{k-1} a_{i_k}~
Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \leq 10^{6})~ là số lượng ô của băng số;
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, \dots, a_{n}~ ~(a_{i} \leq 10^{4}, i = 1, 2, \dots, n)~ ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.
Output
- Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.
Giới hạn
60% số tests ứng với 60% số điểm của bài có ~1 \leq n \leq 20~.
Sample Input
7
4 9 2 4 1 3 7
Sample Output
17
Note
Bình luận
cho em hỏi tại sao không chọn hết vậy ạ? Theo em nếu chọn hết thì nó sẽ là: 9 - 2 + 4 - 1 + 7 - 3 + 4 = 18. Vậy tối đa là 18 chứ sao 17 ạ?
Hình như đề nói "theo thứ tự từ trái sang phải" mà
Hình như đề nói "theo thứ tự từ trái sang phải" mà