DPLINEGAM - Trò chơi với băng số
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
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, ..., 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, ..., i_k~. Khi đó điểm số mà người chơi đạt được sẽ là: ~a_{i_1} - a_{i_2} + ... + (-1)^{k-1}a_{i_k}~
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 chứa số nguyên dương ~N~;
- Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, …, a_N~, mỗi số cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ N ≤ 10^6, 1 ≤ a_i ≤ 10^4~.
Output
- Một số nguyên duy nhất là giá trị lớn nhất có thể thực hiện được ở một lượt chơi.
Sample
Input #1
7
4 9 2 4 1 3 7
Output #1
17
Hint
- Ta lần lượt chọn ~5~ số như hình sau:
Problem source: Chuyên Sơn La Online Judge
Bình luận
cho tôi xin ý tưởng với