CSES - Removal Game | Trò chơi loại bỏ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , nhphucqt
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có một dãy gồm \(n\) số và hai người chơi luân phiên nhau. Tại mỗi lượt, một người chơi loại bỏ đi số đầu tiên hoặc số cuối cùng ra khỏi danh sách, và điểm của người đó tăng thêm một lượng bằng số đó. Cả hai người chơi đều muốn tối đa hóa điểm của họ.

Số điểm tối đa có thể của người chơi thứ nhất là bao nhiêu nếu cả hai người đều chơi tối ưu?

Input

  • Dòng đầu vào đầu tiên chứa một số nguyên \(n\): kích thước của dãy.
  • Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các phần tử của dãy.

Output

  • In số điểm tối đa có thể của người chơi thứ nhất.

Constraints

  • \(1 \le n \le 5000\)
  • \(-10^9 \le x_i \le 10^9\)

Example

Sample input

4
4 5 1 3

Sample output

8

Bình luận