C++で配列内の最長の山（Mountain）を求めるアルゴリズム

配列 A の任意の連続する部分配列 B は、以下の性質を満たすとき「山（マウンテン）」と呼ばれます。

• B のサイズが 3 以上であること
• 0 < i < B.length - 1 を満たすある i が存在し、B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] となること（要素が一度単調に増加した後、単調に減少する形状であること）

ここで、整数の配列 A が与えられたとき、その中で最も長い山の長さを求めることを考えます。山がひとつも存在しない場合は 0 を返します。たとえば入力が [2,1,4,7,3,2,5] の場合、答えは 5 になります。このとき最も大きな山は [1,4,7,3,2] であり、その長さは 5 です。

解法のアプローチ

この問題は、配列を左から順に走査しながら「上り坂」と「下り坂」を検出することで解けます。具体的には、次の手順に従います。

• ret := 0、n := 配列 a のサイズ と初期化します。
• i を 0 から n - 1 まで、処理終了後は i = j + 1 として進めながら、以下を繰り返します。
  • j := i とし、down := false、up := false で初期化します。
  • j + 1 < n かつ a[j + 1] > a[j] の間、up := true として j を 1 増やします（上り坂を探索）。
  • up が true かつ j + 1 < n かつ a[j + 1] < a[j] の間、down := true として j を 1 増やします（下り坂を探索）。
  • up と down がどちらも true の場合、山が成立しているので ret := max(j - i + 1, ret) として最大長を更新し、j を 1 減らして次の走査位置を調整します。
• 最後に ret を返します。

理解を深めるために、以下の C++ 実装を見てみましょう。

例（C++ 実装）

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int longestMountain(vector<int>& a) {
        int ret = 0;
        int n = a.size();
        int j;
        for(int i = 0; i < n; i = j + 1){
            j = i;
            bool down = false;
            bool up = false;
            while(j + 1 < n && a[j + 1] > a[j]) {
                up = true;
                j++;
            }
            while(up && j + 1 < n && a[j + 1] < a[j]){
                down = true;
                j++;
            }
            if(up && down){
                ret = max(j - i + 1, ret);
                j--;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v = {2,1,4,7,3,2,5};
    Solution ob;
    cout << (ob.longestMountain(v));
}

入力

[2,1,4,7,3,2,5]

出力

5

計算量

このアルゴリズムでは、外側のループが進むたびに i は処理済みの区間の直後へジャンプするため、各要素は高々一度しか訪問されません。したがって、時間計算量は O(n)、追加で必要な空間計算量は O(1) と非常に効率的です。