C++で左右の次に大きい要素のインデックス積の最大値を求める方法

このチュートリアルでは、配列内の各要素について「左側の次に大きい要素のインデックス」と「右側の次に大きい要素のインデックス」の積を計算し、その最大値を求めるC++プログラムについて解説します。

問題の概要

整数の配列が与えられます。各要素 i に対して、以下の2つのインデックスを定義します。

• L(i)：現在の要素より大きい値を持つ、左側で最も近い要素のインデックス
• R(i)：現在の要素より大きい値を持つ、右側で最も近い要素のインデックス

そして、すべての要素の中で L(i) × R(i) が最大となる値を求めるのがこの問題の目的です。左右どちらにも大きい要素が存在しない場合は、そのインデックスを 0 として扱います。

アルゴリズムのポイント

素朴な方法では各要素ごとに左右を走査するため O(n²) の計算量が必要になりますが、スタックを活用することで O(n) まで計算量を抑えられます。スタックには要素のインデックス（1始まり）を保持しておき、より大きな要素が出現したタイミングで、スタック内で待機していたインデックスに対して「次に大きい要素の位置」を順次確定させていく仕組みです。

C++での実装例

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

// 左側で次に大きい要素のインデックスを求める
vector<int> nextGreaterInLeft(int a[], int n) {
    vector<int> left_index(MAX, 0);
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top();
            s.pop();
            left_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return left_index;
}

// 右側で次に大きい要素のインデックスを求める
vector<int> nextGreaterInRight(int a[], int n) {
    vector<int> right_index(MAX, 0);
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top();
            s.pop();
            right_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return right_index;
}

// L(i) * R(i) の最大値を求める
int LRProduct(int arr[], int n) {
    vector<int> left = nextGreaterInLeft(arr, n);
    vector<int> right = nextGreaterInRight(arr, n);
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, left[i] * right[i]);
    }
    return ans;
}

int main() {
    int arr[] = { 5, 4, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << LRProduct(arr, n);
    return 0;
}

出力結果

8

処理の流れの解説

入力配列を {5, 4, 3, 4, 5} とした場合を考えてみましょう。

• 3番目の要素（値 3）に対しては、左側で最も近い大きい要素は2番目の「4」、右側で最も近い大きい要素は4番目の「4」です。
• したがって L(3) × R(3) = 2 × 4 = 8 となり、これが全要素の中で最大の積になります。

一方、両端にある要素「5」は、それより大きい値が左右どちらにも存在しないため、対応するインデックスは 0 となり、積は 0 として計算されます。

まとめ

この手法では、スタックを用いて「次に大きい要素」の探索を各要素につき1回ずつ処理するだけで済むため、全体の時間計算量は O(n)、必要なメモリも O(n) に収まります。大きな配列に対しても高速に動作する、実用的で効率的なアプローチと言えるでしょう。