C++で厳密に増加する部分配列の最大和を求めるアルゴリズム

問題の概要

n 個の整数からなる配列が与えられたとき、その中に存在する「厳密に増加する（strictly increasing）部分配列」の中で、要素の合計が最大となるものを求めます。

例として、次のような配列を考えてみましょう。

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

この配列には、厳密に増加している部分配列が3つ存在します。

• {1, 2, 3}
• {2, 5}
• {1, 7}

それぞれの合計は 6、7、8 となり、この中で最大となるのは {1, 7} の合計 8 です。

解き方の考え方

この問題は、現在の部分配列の合計（current_sum）とこれまでの最大合計（max_sum）を追跡しながら配列を一度だけ走査することで、O(n) の計算量で効率よく解けます。

具体的な手順は以下の通りです。

1. 配列の先頭要素を current_sum の初期値とします。
2. 各要素 arr[i] について、直前の要素 arr[i-1] より大きければ、それは同じ増加列の続きなので current_sum に加算します。
3. そうでなければ、そこが新しい部分配列の始点になります。current_sum を更新する前に、必要に応じて max_sum を現在の current_sum で更新します。
<ル>最後に、max_sum と current_sum のうち大きい方を答えとして返します。

C++での実装例

#include<iostream>
using namespace std;

int maximum(int a, int b){
    return (a > b) ? a : b;
}

int maximum_sum_incr_subarr(int array[], int n) {
    int max_sum = 0;
    int current_sum = array[0];

    for (int i = 1; i < n; i++) {
        if (array[i - 1] < array[i])
            current_sum = current_sum + array[i];
        else {
            max_sum = maximum(max_sum, current_sum);
            current_sum = array[i];
        }
    }
    return max(max_sum, current_sum);
}

int main() {
    int arr[] = {1, 2, 3, 2, 5, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum : " << maximum_sum_incr_subarr(arr, n);
}

実行結果

Maximum sum : 8

まとめ

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(n)、追加のメモリ使用量は O(1) ときわめて効率的です。増加列が途切れるタイミングで合計をリセットし、その都度最大値を更新していくというシンプルな発想がポイントです。