指定した値より大きい最大値を持つ部分配列の個数を求めるPythonプログラム

問題の概要

複数の整数が格納された配列があるとします。この配列から取り出せるすべての連続する部分配列（サブアレイ）を列挙し、それぞれの部分配列を「その中の最大要素」で置き換えます。さらに数値 k が与えられたとき、置き換え後の値が k より大きくなる部分配列が何個あるかを求めるのがこの問題です。

例えば、入力が input_array = [5, 6, 7, 8]、k = 7 の場合、出力は 4 になります。

例を使った解説

入力配列 [5, 6, 7, 8] から取り出せる連続する部分配列は、次の10個です。

{5}, {6}, {7}, {8}, {5, 6}, {6, 7}, {7, 8}, {5, 6, 7}, {6, 7, 8}, {5, 6, 7, 8}

各部分配列をその中の最大要素で置き換えると、次のようになります。

{5}, {6}, {7}, {8}, {6}, {7}, {8}, {7}, {8}, {8}

このうち、値が 7 より大きいものは {8} が4回現れるため、4個となります。

解法のアプローチ：補集合の活用

すべての部分配列を実際に生成すると計算量が膨大になるため、ここでは「補集合」の考え方を使った効率的な手法を採用します。

長さ n の配列に含まれる連続する部分配列の総数は n × (n + 1) / 2 個です。そこで、

• 全体の部分配列の数
• 「すべての要素が k 以下である部分配列」の数

の差を取れば、「最大値が k より大きい部分配列」の個数が求まります。

具体的な手順

• count := 0、consecutive := 0 で初期化する
• input_array の各要素 x について以下を繰り返す
  • x > k の場合 → consecutive := 0（連続が途切れたためリセット）
  • それ以外の場合 → consecutive を1増やし、count に consecutive を加算する
• 最後に「n × (n + 1) / 2 − count」を返す

ここで consecutive の累積加算により、k 以下の要素が m 個連続している区間では 1 + 2 + … + m = m × (m + 1) / 2 個の部分配列が自動的に数え上げられる仕組みです。

実装例

それでは、以下のPythonコードを見てみましょう。

def solve(input_array, k):
    count = 0
    consecutive = 0
    for x in input_array:
        if x > k:
            consecutive = 0
        else:
            consecutive += 1
            count += consecutive
    return len(input_array) * (len(input_array) + 1) // 2 - count

print(solve([5, 6, 7, 8], 7))

入力

[5, 6, 7, 8], 7

出力

4

まとめ

このアルゴリズムは配列を一度走査するだけで済むため、時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。部分配列を全列挙する O(n²) 以上の素朴な方法と比べ、大きな入力に対しても高速に動作する点が大きなメリットです。