atcoderにおけるedpcの問題Lについて

Question

標記の件、参加者様の書かれたコードを読んでいて不明点があったのでご質問します。

問題は、L-Dequeです。
https://atcoder.jp/contests/dp/tasks/dp_l

問題の引用

最初に、数列a=(a1​,a2​,…,aN​) が与えられます。
a が空になるまで、二人は次の操作を交互に行います。 先手は太郎君です。
a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人はx 点を得る。
ゲーム終了時の太郎君の総得点をX、次郎君の総得点を Y とします。 太郎君は X−Y を最大化しようとし、次郎君はX−Y を最小化しようとします。
二人が最適に行動すると仮定したとき、X−Y を求めてください。

解答コードの引用

import numpy as np
 
n = int(input())
a = np.array([int(i) for i in input().split()], dtype=np.int64)
 
s = np.copy(a)
for i in range(1, n):
s = np.maximum(a[:n-i]-s[1:n-i+1], a[i:]-s[:n-i])
 
print(s[0])

処理の核の部分としては、np.maximumで与えられた配列を一つずつずらして引き算→大きい方（負数でない方？）を選択する部分なんだと思いますが、なぜこうすると最適な解が出るのかがわかりません。

よろしくお願いいたします。

Answer 1

その参考にしている解答コードはエッセンスを圧縮して書いてあるので、
いきなり理解するのは難しいと思います。

入力例1(N = 4, A = [10, 80, 90, 30])の場合で、
数列のl番目からr番目(l <= r)までが使える場合のX-Yを2次元の
dp表にして作っていくと分かりやすいのではないかと思います。

最初に l=r=0, l=r=1, l=r=2, ... のように数列の中の数字1つだけを使える場合を考えると
表は以下のようになると思います。(未は未計算)

[10, '未', '未', '未']
['未', 80, '未', '未']
['未', '未', 90, '未']
['未', '未', '未', 30]

次に (l=0, r=1), (l=1, r=2), ...のように数字が2つ使用できる場合を考えて
dp表を更新すると以下のようになります。

[10, 70, '未', '未']
['未', 80, 10, '未']
['未', '未', 90, 60]
['未', '未', '未', 30]

使える数字を増やしながら表を更新していくと、最終的には以下のようになり、
数列の数字全てを使用した場合のX-Yは10という答えが出てきます。

[10, 70, 20, 10]
['未', 80, 10, 20]
['未', '未', 90, 60]
['未', '未', '未', 30]

質問に貼ってもらった解答コードをステップ実行してsの内容を見ていくと、
以下のようになっていることが分かります。

[10, 80, 90, 30]
[70, 10, 60]
[20, 20]
[10]

これは、上で計算したdp表の左上から右下への斜めの部分の数字の並びと同じになっています。
質問にある解答コードは、numpyの機能をうまく使うことで、わざわざ2次元の表をつくらずに
欲しい答えを求めているのだと思います。