C++で絶対値式の最大値を効率的に求めるアルゴリズム

問題概要

同じ長さを持つ2つの整数配列が与えられたとき、次の式の最大値を求めることを考えます。

|arr1[i] − arr1[j]| + |arr2[i] − arr2[j]| + |i − j|

ここで、最大値は 0 ≤ i, j < arr1.length を満たすすべての組み合わせについて評価します。たとえば、配列 [1,2,3,4] と [-1,4,5,6] が与えられた場合、答えは 13 になります。

解法のアプローチ

すべての (i, j) の組み合わせを素朴に調べると計算量は O(n²) になりますが、絶対値を展開して式を整理すると O(n) で解くことができます。ポイントは、3つの絶対値の符号の組み合わせは 2³ = 8 通りありますが、式全体にマイナスを掛けても絶対値の値は変わらないため、本質的には4通りのパターンに帰着できるという点です。

具体的には、次の手順で解きます。

• 配列 v を受け取り、その要素の最大値と最小値の差を返すメソッド getVal を定義します
  • maxVal := −∞、minVal := +∞ で初期化
  • i を 0 から v のサイズまでループし、minVal := min(v[i], minVal)、maxVal := max(v[i], maxVal) を更新
  • maxVal − minVal を返す
• メインの処理では以下を実行します
  • サイズ4の配列 ret を用意する
  • n := arr1 のサイズとする
  • i を 0 から n−1 までループし、次の4つの値をそれぞれ格納する
    • ret[0] ← arr1[i] − arr2[i] + i
    • ret[1] ← arr1[i] + arr2[i] + i
    • ret[2] ← arr1[i] − arr2[i] − i
    • ret[3] ← arr1[i] + arr2[i] − i
  • ans := −∞ で初期化
  • i を 0 から 3 までループし、ans := max(ans, getVal(ret[i])) を更新
  • ans を返す

この手法が正しく機能するのは、「(arr1[i] ± arr2[i] ± i) − (arr1[j] ± arr2[j] ± j)」という形の式の最大値は、対応する変換後の配列の最大値と最小値の差で表せるためです。4つのパターンそれぞれについてこの差を計算し、その最大値を取れば答えが得られます。

実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int getVal(vector <int>& v){
        int maxVal = INT_MIN;
        int minVal = INT_MAX;
        for(int i = 0; i < v.size(); i++){
            minVal = min(v[i], minVal);
            maxVal = max(v[i], maxVal);
        }
        return maxVal - minVal;
    }
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        vector <int> ret[4];
        int n = arr1.size();
        for(int i = 0; i < n; i++){
            ret[0].push_back(arr1[i] - arr2[i] + i);
            ret[1].push_back(arr1[i] + arr2[i] + i);
            ret[2].push_back(arr1[i] - arr2[i] - i);
            ret[3].push_back(arr1[i] + arr2[i] - i);
        }
        int ans = INT_MIN;
        for(int i = 0; i < 4; i++){
            ans = max(ans, getVal(ret[i]));
        }
        return ans;
    }
};
main(){
    vector<int> v1 = {1,2,3,4}, v2 = {-1, 4, 5, 6};
    Solution ob;
    cout << (ob.maxAbsValExpr(v1, v2));
}

入力

[1,2,3,4]
[-1,4,5,6]

出力

13

計算量の分析

時間計算量: O(n) — 配列を定数回走査するだけで済みます。
空間計算量: O(n) — 変換後の値を格納するための4つの補助配列が必要です。