Có một danh sách gồm n số và hai người chơi di chuyển luân phiên. Trên mỗi nước đi, người chơi xóa số đầu tiên hoặc số cuối cùng khỏi danh sách và điểm của họ sẽ tăng theo số đó. Cả hai người chơi đều cố gắng tối đa hóa điểm số của mình.

Số điểm tối đa có thể cho người chơi đầu tiên khi cả hai người chơi đều chơi tối ưu là bao nhiêu?

Đầu vào:

Dòng đầu tiên chứa số nguyên n: kích thước của danh sách (n\(\leq\)5000).

Dòng tiếp theo có n số nguyên x1, x2,…, xn: nội dung của danh sách.

Đầu ra:

In số điểm tối đa có thể cho người chơi đầu tiên.