C++で部分配列を反転して配列の値を最大化するアルゴリズム

問題概要

整数型の配列 nums が与えられます。この配列の「値」は、すべてのインデックス i（0 ≤ i ≤ n−2）における |nums[i] − nums[i+1]| の総和として定義されます。ここで n は配列のサイズです。

私たちは配列内の任意の部分配列を選んで反転することができ、この操作は一度だけ実行できます。操作を行った後の最終的な配列の値として考えられる最大値を求めてください。

たとえば、入力が [1, 5, 4, 2, 3] の場合、出力は 10 になります。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

• ret := 0、extra := 0 で初期化します。
• n := nums のサイズとします。
• minVal := 無限大、maxVal := −無限大 で初期化します。
• i := 0 から n − 2 まで、i を 1 ずつ増やしながらループします。
  • a := nums[i]、b := nums[i + 1] とします。
  • ret := ret + |b − a|（現在の配列の値を累積）
  • extra := max(extra, |nums[0] − b| − |a − b|)
  • extra := max(extra, |nums[n − 1] − a| − |a − b|)
  • maxVal := max(maxVal, min(a, b))
  • minVal := min(minVal, max(a, b))
• ret + max(extra, (maxVal − minVal) × 2) を返します。

考え方のポイント

部分配列を反転しても、値が変化するのは反転区間の両端に隣接する境界部分だけです。したがって、すべての反転候補を総当たりする必要はありません。配列の先頭・末尾と接続される場合の増分（extra）と、隣接ペアの最小値・最大値から導かれる一般ケース（(maxVal − minVal) × 2）の2パターンを評価すればよく、これにより O(n) の計算量で最適解を求められます。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxValueAfterReverse(vector<int>& nums) {
        int ret = 0;
        int extra = 0;
        int n = nums.size();
        int minVal = INT_MAX;
        int maxVal = INT_MIN;
        for(int i = 0; i < n - 1; i++){
            int a = nums[i];
            int b = nums[i + 1];
            ret += abs(b - a);
            extra = max(extra, abs(nums[0] - b) - abs(a - b));
            extra = max(extra, abs(nums[n - 1] - a) - abs(a - b));
            maxVal = max(maxVal, min(a, b));
            minVal = min(minVal, max(a, b));
        }
        return ret + max(extra, (maxVal - minVal) * 2);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,5,4,2,3};
    cout << (ob.maxValueAfterReverse(v));
}

入力

{1,5,4,2,3}

出力

10