0. はじめに
数年前の問題ですが、一昨日解いて解説記事を調べると「負の符号の数」を使った解説記事が多く、動的計画法（DP）で解いたという記事が少ないので、需要はともかく書いておきます。
有名所のはまやんさんとけんちょんさんの記事では「負の符号の数」を考慮して解を得ています。
PythonとDPによる解説記事としては56さんの記事があります。
同じ内容では意味がないので、詳細を丁寧に書こうと思います。
要素のインデックスは0始まりです。
1. 問題とACコード
n = int(input())
a = list( map(int, input().split()) )
inf = float("inf")
dp = [[-inf, -inf] for _ in range(n+1)]
dp[0] = [0, -inf]
for i in range(n-1):
# A_{i-1}に-1が乗算されていないとき
dp[i+1][0] = max(dp[i+1][0], dp[i][0] + a[i])
dp[i+1][1] = max(dp[i+1][1], dp[i][0] - a[i])
# A_{i-1}に-1が乗算されているとき
dp[i+1][0] = max(dp[i+1][0], dp[i][1] - a[i])
dp[i+1][1] = max(dp[i+1][1], dp[i][1] + a[i])
i=n-1
dp[i+1][0] = max(dp[i+1][0], dp[i][0] + a[i])
dp[i+1][0] = max(dp[i+1][0], dp[i][1] - a[i])
#for i in range(n+1):
# print(dp[i])
print(max(dp[-1]))
2. 考察
2.1 状態数の見積もり
問題の肝は、「『$A_i$と$A_{i+1}$に$−1$を乗算する』操作を任意で行い、変換後の数列の和の最大値を求めよ」です。なので、操作をするかしないかの状態変化を全て調べれば、最大の和を取る状態が一つ見つけられます。
しかし数列の長さが最大で$10^5$なので、数列の一要素ごとに操作の実行・不実行を選択して状態数を2倍にすると、最終的な状態数は$2^{100000}\sim10^{30000}$となります（$2^{10}=1024\sim10^3$）。もちろんこの状態数は時間内で計算できません。
そこで問題文の中に「和の最大値を求めよ」とあるので、要素ごとに操作の実行・不実行で状態を分けてそれまでの和の最大値をメモ化すれば、DPで解けるだろうと推測（期待）できます。
2.2 状態遷移
状態遷移についてです。
- 考慮する状態は、「$A_i$に$-1$を乗算したとき、しなかったときの和」
- $dp[i+1][0]$、 $A_i$に$-1$を乗算しなかったときの和。
- $dp[i+1][1]$、 $A_i$に$-1$を乗算したときの和。
- 前の要素$A_{i-1}$に$-1$が乗算されていないとき（つまり$dp[i][0]$に新たな要素を加えるとき）は、以下のように実装します。
- $dp[i+1][0] = \max(dp[i+1][0], dp[i][0]+A_i)$
- $dp[i+1][1] = \max(dp[i+1][1], dp[i][0]-A_i)$
上の遷移式が$-1$を乗算しない時の和、下の遷移式が$-1$を乗算した時の和です。下の遷移式では$-1$を乗算して和を求めているので、値は$dp[i+1][1]$に格納されます。
- 前の要素$A_{i-1}$に$-1$が乗算されているときは（つまり$dp[i][1]$に新たな要素を加えるとき）、以下のように実装します。
- $dp[i+1][0] = \max(dp[i+1][0], dp[i][1]-A_i)$
- $dp[i+1][1] = \max(dp[i+1][1], dp[i][1]+A_i)$
ここでのポイントは、$A_i$の符号です。
$dp[i][1]$を考えるときは、「$A_{i-1}$に$-1$が乗算されて」いる前提であり、この時点で$A_i$にも$-1$が乗算されています。従って$A_i$に改めて$-1$を乗算しなければ、$dp[i][1]$に$-A_i$を加えた和が$dp[i+1][0]$に格納されます。一方、$A_i$に改めて$-1$を乗算すると、$dp[i][1]$に$+A_i$を加えた和が$dp[i+1][1]$に格納されます。
この状態遷移を理解していると、最後の、$-1$を乗算するかしないかを選択できない$A_{n-1}$についての遷移式もシンプルに書けます。
2.3 DPの初期値
さらに、DPの初期値にも注意が必要です。初期値を$dp[0]=[0, 0]$とすると失敗します。正解は、$dp[0]=[0, -\inf]$です。
なぜなら、$A_0$による和を考えるときは、$A_{-1}$と$A_0$に$-1$が乗算されているとは考えないからです。正しい計算のためには、事前に$-1$が乗算されていない$A_0$に$-1$を乗算するかどうかの選択をしなければなりません。このために、初期値は$dp[0]=[0, -\inf]$である必要があります。
3. おわりに
私のコードよりも、先に紹介した56さんのコードのほうがシンプルです。そちらも参考にどうぞ。
（正直、最初から理解していたかのように書いていますが、実装した時は理解が曖昧で正解が出ませんでした。）