Phép toán với ngăn xếp hai đầu

Xem PDF

Điểm: 550 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(Kaninho\)\(Henry\) chơi với nhau một trò chơi như sau:

Ban đầu, họ được cho một dãy số \(a=(a_1,a_2,\cdots,a_n)\). Họ lần lượt thực hiện phép toán dưới đây cho đến khi dãy \(a\) rỗng, bắt đầu từ \(Kaninho\):

Loại bỏ phần tử đầu tiên hoặc cuối cùng của dãy \(a\). Người chơi đó sẽ kiếm được \(x\) điểm, với \(x\) là phần tử bị loại bỏ.
Gọi \(X\)\(Y\) lần lượt là số điểm của \(Kaninho\)\(Henry\) sau khi trò chơi kết thúc. \(Kaninho\) cố gắng làm \(X−Y\) lớn nhất có thể, trong khi \(Henry\) muốn \(X−Y\) nhỏ nhất có thể.

Giả sử cả hai người đều chơi tối ưu, tìm giá trị của \(X−Y\).

Input

  • Dòng thứ nhất chứa số nguyên \(N(1 \leq N \leq 3000)\)
  • Dòng thứ hai, chứa \(n\) số nguyên \(a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)\)

Output

  • In ra giá trị cần tìm

Example

Test 1

Input
4
10 80 90 30 
Output
10
Note

Quá trình chơi tối ưu của hai người chơi như sau:

  • \(Kaninho\):\((10,80,90,30)\)\((10,80,90)\)
  • \(Henry\):\((10,80,90)\)\((10,80)\)
  • \(Kaninho\):\((10,80)\)\((10)\)
  • \(Henry\):\((10)\)\(()\)

Ở đây \(X=30+80=110\)\(Y=90+10=100\)


Bình luận


  • 0
    SPyofgame    9:47 p.m. 17 Tháng 8, 2020

    Suggest bài toán khó hơn với K hàng đợi 10^6 phần tử


    • 0
      Vinht1k60    8:52 a.m. 4 Tháng 8, 2020

      Vẫn là đệ quy có nhớ :v

      1 phản hồi