問題の言い換え

この言い換えは こちらの解説 と同一の内容です。

部分列のスコアに寄与するのは、列に含まれる要素の最大値と最小値のみです。よって、部分列の端にあって、部分列の最小値でも最大値でもない要素は無視できます。

このことから、問題を次のように言い換えても求める答えが同じであることがわかります。

長さ \(N\) の数列 \(A\) が与えられます。この数列から、いくつかの連続する空でない部分列を、部分列同士が交わりをもたないように選びます。

最適に部分列を選んだときの、選んだ部分列のスコアの和の最大値を求めてください。

また、言い換え後の問題で選ぶ部分列は、次のいずれかに限定してよいです。

• 部分列の左端が部分列の最小値であり、右端が部分列の最大値である
• 部分列の左端が部分列の最大値であり、右端が部分列の最小値である

動的計画法の適用

動的計画法で使う配列 \(\mathrm{dp}\) を次のように定めます。

• \(\mathrm{dp}[i][S] :=\) \(i\) 番目の要素までを見ており、現在作っている区間の状態が \(S\) であるときのスコアの和の最大値

\(S\) はサイズ 2 の集合であり、最小値が入っている/いない・最大値が入っている/いない の計 4 状態を取りえます。

配列を更新するときは、以下の遷移を考えればよいです。

• \(a_i\) を最小値として使う
  • 現在作っている区間に最小値が入っていない場合にのみ可能
  • 集合 \(S\) を、最小値が入っている状態に更新。最小値も最大値も入っている状態になったとき、区間を閉じる
• \(a_i\) を最大値として使う
  • 現在作っている区間に最大値が入っていない場合にのみ可能
  • 集合 \(S\) を、最大値が入っている状態に更新。最小値も最大値も入っている状態になったとき、区間を閉じる
• それ以外
  • いつでも可能であり、集合 \(S\) の状態は変化しない

\(a_i\) が実際に区間内の最小値・最大値かどうかを確認する必要はない点にご注意ください。

この動的計画法で取りうる値は最適解以下であり、また最適解を含むことが証明できます。よって、この方針で解くことができます。

計算量は \(O(N)\) です。

実装例 (C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
using namespace std;
using ll = long long int;
const ll INF = 1LL << 60;

ll dp[200010][4];
int main() {
    int N; cin >> N;
    fill(dp[0], dp[N+1], -INF);
    dp[0][0] = 0;
    for(int i=0; i<N; i++) {
        ll a; cin >> a;
        for(int bit=0; bit<4; bit++) {
            // 区間の最小値にも最大値にもしない場合
            dp[i+1][bit] = max(dp[i+1][bit], dp[i][bit]);
            // 区間の最小値にする場合
            if(!(bit & 1)) dp[i+1][bit|1] = max(dp[i+1][bit|1], dp[i][bit] - a);
            // 区間の最大値にする場合
            if(!(bit & 2)) dp[i+1][bit|2] = max(dp[i+1][bit|2], dp[i][bit] + a);
        }
        // 最小値と最大値が両方入った区間を閉じる操作に対応
        dp[i+1][0] = max(dp[i+1][0], dp[i+1][3]);
    }
    cout << dp[N][0] << endl;
    return 0;
}