C++で解く！配列の左右にある次に大きい要素のインデックスの最大積を求める方法

この記事では、配列 arr[] が与えられたときに、「左側・右側にある次に大きい要素のインデックスの積」の最大値を計算するC++プログラムを作成する方法を解説します。

問題の概要

与えられた配列に対して、left[i] * right[i] の最大値を求める必要があります。ここで、left配列とright配列はそれぞれ次のように定義されます。

left[i] = j ： arr[i] < arr[j] かつ i > j を満たすj
right[i] = j ： arr[i] < arr[j] かつ i < j を満たすj
※ 配列は1始まりのインデックスです。

つまり、各要素について「左方向で最初に出会うより大きい要素のインデックス」と「右方向で最初に出会うより大きい要素のインデックス」を掛け合わせ、その中で最も大きな値を答えとします。

入出力例

入力

arr[6] = {5, 2, 3, 1, 8, 6}

出力

15

説明

left配列とright配列を作成すると、次のようになります。

left[]  = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}

インデックスごとの積：
1 → 0*5 = 0
2 → 1*3 = 3
3 → 1*5 = 5
4 → 3*5 = 15
5 → 0*0 = 0
6 → 0*5 = 0

この中で最大となるのはインデックス4における 3×5 = 15 です。したがって、答えは 15 となります。

解法のアプローチ

各要素の左右にある「より大きい要素」のインデックスの最大積を求めるためには、まず左側と右側それぞれについて、そのような要素のインデックスを特定し、その積を記録して比較します。

左右の大きい要素を効率的に見つけるには、スタックを利用します。具体的には、次のような操作を行います。

・スタックが空の場合 → 現在のインデックスをプッシュし、tos = 1 とする（tosはスタックの先頭）
・それ以外で arr[i] > arr[tos] の場合 → tos の位置を更新する

この手法により、配列の左側・右側それぞれについて、対象の要素よりも大きい要素のインデックスをすべて求めることができます。スタックを使うことで、単純な全探索（O(n²)）よりも効率的に処理できます。

C++による実装例

以下は、この解法の動作を示すプログラムです。

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

int* findNextGreaterIndex(int a[], int n, char ch) {
    int* greaterIndex = new int[n];
    stack<int> index;
    if (ch == 'R') {
        for (int i = 0; i < n; ++i) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    }
    else if (ch == 'L') {
        for (int i = n - 1; i >= 0; i--) {
            while (!index.empty() && a[i] > a[index.top() - 1]) {
                int indexVal = index.top();
                index.pop();
                greaterIndex[indexVal - 1] = i + 1;
            }
            index.push(i + 1);
        }
    }
    return greaterIndex;
}

int calcMaxGreaterIndexProd(int arr[], int n) {
    int* left = findNextGreaterIndex(arr, n, 'L');
    int* right = findNextGreaterIndex(arr, n, 'R');
    int maxProd = -1000;
    int prod;
    for (int i = 1; i < n; i++) {
        prod = left[i] * right[i];
        if (prod > maxProd)
            maxProd = prod;
    }
    return maxProd;
}

int main() {
    int arr[] = { 5, 2, 3, 1, 8, 6 };
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << "左右の次に大きい要素のインデックスの積の最大値は "
         << calcMaxGreaterIndexProd(arr, n);
    return 0;
}

実行結果

左右の次に大きい要素のインデックスの積の最大値は 15

まとめ

この問題は、スタックを活用することで各要素の左右にある次に大きい要素のインデックスを効率的に求められる点がポイントです。計算量はO(n)程度に抑えられ、大きな配列でも高速に動作します。「次に大きい要素（Next Greater Element）」を求めるテクニックは、株価分析やデータ処理など、さまざまな場面で応用できる重要なアルゴリズムなので、ぜひマスターしておきましょう。