C++で1回の部分リスト反転後に隣接要素の絶対差の合計を最大化するプログラム

問題の概要

数値のリスト nums が与えられ、その中の任意の部分リスト(連続する区間)を最大1回だけ反転できるものとします。この操作を行った後、次の式で表される「隣接要素の絶対差の合計」が取り得る最大値を求めます。

Σ_i=0ⁿ⁻² |nums[i+1] − nums[i]|

例えば、入力が nums = [2, 4, 6] の場合を考えてみましょう。部分リスト [4, 6] を反転すると、リストは [2, 6, 4] になります。このとき |2 − 6| + |6 − 4| = 4 + 2 = 6 となるため、出力は 6 です。

解法のアプローチ

すべての反転候補を素朴に試すと計算量が O(n²) になってしまいますが、「反転による影響が現れるのは境界部分の差分だけ」という性質を利用すれば、O(n) で効率的に求められます。具体的には、次の2つのケースに分けて考えます。

• 端を含む反転(先頭または末尾を含む場合):影響を受けるのは境界の1箇所だけなので、単純なループで評価できます。
• 内部のみの反転(両端を含まない場合):反転区間の両側にある2つの境界の差分が変化します。境界値の符号の組み合わせ(pp・pm・mp・mm)ごとに最良候補を保持しながら走査することで、各位置を1度ずつ確認するだけで済みます。

アルゴリズムの手順

1. nums のサイズが 1 以下の場合は 0 を返します。
2. ans := 0、n := nums のサイズとします。
3. i = 1 から n−1 までループし、ans += |nums[i] − nums[i−1]| として元の合計を計算します。
4. orig := ans として元の値を保存します。
5. i = 1 から n−2 までループし、次の2通りで ans を更新します。
   • ans = max(ans, orig − |nums[i] − nums[i+1]| + |nums[0] − nums[i+1]|)(先頭を含む反転)
   • ans = max(ans, orig − |nums[i] − nums[i−1]| + |nums[n−1] − nums[i−1]|)(末尾を含む反転)
6. pp、pm、mp、mm を次のように初期化します。
   • pp := −|nums[1] − nums[0]| + nums[0] + nums[1]
   • pm := −|nums[1] − nums[0]| + nums[0] − nums[1]
   • mp := −|nums[1] − nums[0]| − nums[0] + nums[1]
   • mm := −|nums[1] − nums[0]| − nums[0] − nums[1]
7. j = 2 から n−2 までループします。
   • jerror := |nums[j+1] − nums[j]| とします。
   • ans を「orig + pp / pm / mp / mm − jerror ± nums[j] ± nums[j+1]」の4通りと比較して最大値を取ります。
   • pp、pm、mp、mm を「−|nums[j] − nums[j−1]| ± nums[j−1] ± nums[j]」で更新します。
8. ans を返します。

C++ 実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& nums) {
    if (nums.size() <= 1)
        return 0;
    int ans = 0;
    int n = nums.size();
    // 元の隣接絶対差の合計を計算
    for (int i = 1; i < n; i++) {
        ans += abs(nums[i] - nums[i - 1]);
    }
    int orig = ans;
    // 先頭または末尾を含む反転を評価
    for (int i = 1; i < n - 1; i++) {
        ans = max(ans, orig - abs(nums[i] - nums[i + 1])
                       + abs(nums[0] - nums[i + 1]));
        ans = max(ans, orig - abs(nums[i] - nums[i - 1])
                       + abs(nums[n - 1] - nums[i - 1]));
    }
    // 内部のみの反転用に4種類の最良候補を初期化
    int pp = -abs(nums[1] - nums[0]) + nums[0] + nums[1];
    int pm = -abs(nums[1] - nums[0]) + nums[0] - nums[1];
    int mp = -abs(nums[1] - nums[0]) - nums[0] + nums[1];
    int mm = -abs(nums[1] - nums[0]) - nums[0] - nums[1];
    for (int j = 2; j < n - 1; j++) {
        int jerror = abs(nums[j + 1] - nums[j]);
        ans = max(ans, orig + pp - jerror - nums[j] - nums[j + 1]);
        ans = max(ans, orig + pm - jerror - nums[j] + nums[j + 1]);
        ans = max(ans, orig + mp - jerror + nums[j] - nums[j + 1]);
        ans = max(ans, orig + mm - jerror + nums[j] + nums[j + 1]);
        pp = max(pp, -abs(nums[j] - nums[j - 1]) + nums[j - 1] + nums[j]);
        pm = max(pm, -abs(nums[j] - nums[j - 1]) + nums[j - 1] - nums[j]);
        mp = max(mp, -abs(nums[j] - nums[j - 1]) - nums[j - 1] + nums[j]);
        mm = max(mm, -abs(nums[j] - nums[j - 1]) - nums[j - 1] - nums[j]);
    }
    return ans;
}

int main() {
    vector<int> v = {2, 4, 6};
    cout << solve(v);
}

入力

{2, 4, 6}

出力

6

この結果は、冒頭の例の通り [4, 6] を反転して [2, 6, 4] としたときの |2 − 6| + |6 − 4| = 6 に対応しています。

計算量

時間計算量は O(n)、追加のメモリ使用量は O(1) です。リスト全体を数回走査するだけで答えが得られるため、要素数が多い入力でも高速に動作します。