C++で全要素がKより大きい部分配列の個数を数える方法

整数型の配列 arr[] と数値 K が与えられます。このとき、すべての要素が K より大きい部分配列(サブアレイ)の総数を求めるのが目標です。

例えば、配列が [1,2,3]、K=1 の場合、条件を満たす部分配列は [2]、[3]、[2,3] の3つになります。

具体的な例で確認してみましょう。

入力 − arr[] = { 2, 2, 1, 1, 1, 5 }; K=1

出力 − 全要素がKより大きい部分配列の個数 − 4

説明 − 条件を満たす部分配列は [2]、[2]、[5]、[2,2] の4つです。それぞれの部分配列に含まれる要素はすべて1より大きくなっています。

入力 − arr[] = { 3,4,5,6 }; K=2

出力 − 全要素がKより大きい部分配列の個数 − 10

説明 − [3]、[4]、[5]、[6]、[3,4]、[4,5]、[5,6]、[3,4,5]、[4,5,6]、[3,4,5,6] の合計10個です。

プログラムで使用するアプローチ

forループを使って配列を先頭から順に走査します。現在の要素が K より大きければカウント(count)を1増やし、そうでなければそれまでの連続区間から作れる部分配列の数 count×(count+1)/2 を合計(total)に加算して count を 0 にリセットします。連続する n 個の要素からは n×(n+1)/2 個の部分配列が作れるため、この式で各区間の組み合わせ数を一括して計算できます。ループ終了後に count が 0 でなければ、末尾の未処理区間分も同様に加算します。

• 数値の配列 arr[] を用意します。

• 関数 sub_greater_k(int arr[], int size, int k) は、配列とそのサイズ、基準値 k を受け取り、全要素が k より大きい部分配列の個数を返します。

• 初期状態として count を 0 に設定します。

• forループで i=0 から i<size まで配列を走査します。

• arr[i] > k であれば count をインクリメントします。

• k より大きい要素が count 個連続している区間に含まれる部分配列の数は count×(count+1)/2 となるので、これを total に加算します。

• ループ終了後、count が 0 でなければ、残りの区間分として count×(count+1)/2 を total に加算します。

• total を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
    int count = 0;
    int total = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] > k){
            count++;
        }
        else{
            total += (count) * (count + 1) / 2;
            count = 0;
        }
    }
    if(count){
        total += (count) * (count + 1) / 2;
    }
    return total;
}
int main(){
    int arr[] = {2, 4, 6, 1, 3, 7, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 7;
    cout<<"Count of subarrays with all elements greater than K are: "<<sub_greater_k(arr, size, k);
    return 0;
}

出力

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

Count of subarrays with all elements greater than K are: 1