C++で最大要素がkより大きい部分配列の数を求める方法

問題概要

整数要素を含む配列 arr[] と変数 k が与えられます。求めるのは、最大要素が k より大きい部分配列の個数です。

たとえば、配列が [1,2,3]、k が 1 の場合、考えられる部分配列は [1], [2], [3], [1,2], [2,3], [1,2,3] の6つです。このうち最大要素が 1 より大きいのは [2], [3], [1,2], [2,3], [1,2,3] の5つなので、答えは 5 となります。

入出力例

例1

入力: arr[] = {1,2,5,3}, k = 3

出力: 最大要素が k より大きい部分配列の数: 6

説明: すべての部分配列は [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3] の10個です。このうち最大要素が 3 より大きいのは、要素 5 を含む次の6つです。

[5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]

例2

入力: arr[] = {1,2,3,4,5}, k = 4

出力: 最大要素が k より大きい部分配列の数: 5

説明: 4 より大きい要素は 5 のみです。したがって、5 を含む次の5つの部分配列が該当します。

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

解法のアプローチ

まず、要素数 n の配列に含まれる部分配列の総数は n×(n+1)/2 であることを利用します。

次に、「すべての要素が k 以下」である部分配列の数を数えます。こうした部分配列は最大要素が k 以下のため条件を満たしません。具体的には、k より大きい要素を区切りとして配列を分割し、連続する「k 以下の要素」の区間ごとに長さ l を求め、それぞれ l×(l+1)/2 を加算していきます。この合計を X とすると、答えは n×(n+1)/2 − X で求められます。

この方法なら、全部分配列を実際に列挙することなく O(n) の計算量で答えを得られるのが大きな利点です。

アルゴリズムの手順

• 整数配列 arr[] と変数 k を入力として受け取ります。
• 関数 maximum_k(int arr[], int size, int k) は、配列・k・配列の長さを受け取り、最大要素が k より大きい部分配列の数を返します。
• カウント用変数 count を 0 で初期化します。
• while ループで、インデックス i = 0 から i < size まで配列を走査します。
• arr[i] > k の場合は continue 文でスキップします(ここが区切りになります)。
• それ以外の場合は、内側の while ループで連続する「k 以下の要素」の長さを数えます。
• i < size かつ arr[i] <= k の間、i と temp(区間の長さ)をインクリメントします。
• 内側のループを抜けたら、temp×(temp+1)/2 を計算して count に加算します。
• 外側のループが終わった時点で、count には「すべての要素が k 以下」の部分配列の総数が入っています。
• 最後に、全部分配列の数 size×(size+1)/2 から count を引いた値を結果として返します。

C++実装例

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

int maximum_k(int arr[], int size, int k){
    int count = 0;
    int i = 0;
    while (i < size){
        // kより大きい要素はスキップ(区切りとして扱う)
        if (arr[i] > k){
            i++;
            continue;
        }
        int temp = 0;
        // 連続してk以下の要素が続く長さを数える
        while (i < size && arr[i] <= k){
            i++;
            temp++;
        }
        // 長さtempの区間から作れる部分配列の数を加算
        int temp_2 = temp * (temp + 1);
        count = count + temp_2 / 2;
    }
    // 全部分配列数から、最大要素がk以下の部分配列数を引く
    count = (size * (size + 1) / 2 - count);
    return count;
}

int main(){
    int arr[] = { 4, 1, 2, 7, 8, 3 };
    int k = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays whose maximum element is greater than k are: " << maximum_k(arr, size, k);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of subarrays whose maximum element is greater than k are: 14

この例では、配列 {4, 1, 2, 7, 8, 3} の全部分配列は 6×7/2 = 21 個あります。「すべての要素が 5 以下」の部分配列は、区間 {4,1,2} から 3×4/2 = 6 個、区間 {3} から 1 個の合計 7 個なので、21 − 7 = 14 が答えとなります。