C++で配列arr[]内のabs(i – j) * min(arr[i], arr[j])の最大値を求める方法

この問題では、N個の整数値からなる配列 arr[] が与えられます。私たちのタスクは、配列 arr[] 内で abs(i – j) * min(arr[i], arr[j]) の最大値を見つけることです。

問題の説明 ― 2つの要素のうち小さい方の値と、そのインデックス同士の絶対差を掛け合わせた積の最大値を求める必要があります。つまり、2つのインデックス i と j に対して、abs(i - j) * min(arr[i], arr[j]) を最大化するのが目標です。

入力例

arr[] = {5, 7, 3, 6, 4}

出力例

16

説明

最大値は16で、インデックス0と4の組み合わせで得られます。
=> abs(0 - 4) * min(arr[0], arr[4])
=> 4 * min(5, 4) => 4 * 4 = 16

解法アプローチ

最も単純な解法は、ネストされたループ（二重ループ）を使う方法です。2つのループを回して各ペア (i, j) ごとに値を計算し、見つかったすべての値の中から最大値を返します。

このアプローチは正しく動作しますが、時間計算量は O(n²) のオーダーとなり、配列サイズが大きくなると非効率になります。

より効率的な解法は、2つのイテレータ（ポインタ）を使用する方法です。1つは配列の先頭から、もう1つは配列の末尾からスタートします。各位置のペアについて必要な値を計算し、比較しながら最大値を maxVal 変数に格納していきます。この処理を2つのイテレータが交差するまで繰り返し、最後に maxVal を返します。

この手法が機能する理由は、毎回小さい方の要素側のポインタを内側へ移動させることで、「距離が縮まる分はより大きな min 値で補える可能性がある」ケースだけを効率よく探索できるためです。これにより時間計算量は O(n) に抑えられます。

この解法の動作を示すプログラム：

コード例

#include<iostream>
using namespace std;
int calcMaxProdValue(int arr[], int n) {
    int maxVal = -100;
    int currentVal;
    int start = 0, end = n-1;
    while (start < end) {
        if (arr[start] < arr[end]) {
            currentVal = arr[start]*(end-start);
            start++;
        }
        else {
            currentVal = arr[end]*(end-start);
            end--;
        }
        maxVal = max(maxVal, currentVal);
    }
    return maxVal;
}
int main(){
    int arr[] = {5, 7, 3, 6, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列における abs(i – j) * min(arr[i], arr[j]) の最大値は "<<calcMaxProdValue(arr,n);
    return 0;
}

出力

配列における abs(i – j) * min(arr[i], arr[j]) の最大値は 16