C++で非増加部分配列の個数を数える方法

正の整数を格納した配列 arr[] が与えられます。この問題の目標は、長さ1以上の「非増加(各要素が直前の要素以下)」となる部分配列の個数を求めることです。例えば、arr[] = {1,3,2} の場合、条件を満たす部分配列は {1}、{2}、{3}、{3,2} の4つになります。

入力例と出力例

例1

入力:

arr[] = {5,4,5}

出力:

非増加部分配列の個数: 7

説明:

該当する部分配列は以下の通りです。
{5}, {4}, {5}, {5,4}

例2

入力:

arr[] = {10,9,8,7}

出力:

非増加部分配列の個数: 10

説明:

該当する部分配列は以下の通りです。
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7},
{10,9,8}, {9,8,7}, {10,9,8,7}

解法のアプローチ

このアプローチでは、「配列 arr[] のインデックス i から j までの要素が非増加でない場合、i から j+1、j+2 … j+n−1 までの範囲も決して非増加にはならない」という性質を利用します。そのため、要素が非増加である限り現在の部分配列の長さを伸ばし続け、より小さい要素 arr[j] < arr[j−1] が見つかった時点で、それまでの非増加区間(長さ len)から作れる部分配列の総数「len × (len + 1) ÷ 2」を答えに加算し、長さを1にリセットします。

• 整数型配列 arr[] を用意します。
• 関数 subarrays(int arr[], int size) は、配列とそのサイズを受け取り、非増加部分配列の個数を返します。
• カウント count を0、部分配列の初期長 temp を1として初期化します。
• for ループで arr[] を走査し、arr[i + 1] <= arr[i] が成り立つ場合は部分配列が非増加であるため temp を1増やします。
• 成り立たない場合は、長さ temp の非増加区間に含まれる部分配列の数「(temp + 1) × temp ÷ 2」を count に加算します。
• 新しい部分配列のために temp を1に戻します。
• すべてのループ終了後、temp > 1 の場合は末尾の非増加区間についても「(temp + 1) × temp ÷ 2」を count に加算します。
• count を結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
    int count = 0;
    int temp = 1;
    for(int i = 0; i < size - 1; ++i){
        if (arr[i + 1] <= arr[i]){
            temp++;
        } else {
            count += (((temp + 1) * temp) / 2);
            temp = 1;
        }
    }
    if(temp > 1){
        count += (((temp + 1) * temp) / 2);
    }
    return count;
}
int main(){
    int arr[] = {2, 6, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"非増加部分配列の個数: "<<subarrays(arr, size);
    return 0;
}

出力

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

非増加部分配列の個数: 7