VOI 09 Bài 1 - Trò chơi với băng số

View as PDF

Submit solution


Points: 0.08 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Thi HSG Quốc gia 2009
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.