C++で最大循環部分配列の合計を求めるアルゴリズム

配列が与えられたとき、その要素を循環的（リング状）につなげた部分配列の中から、合計が最大となるものを求めるのが本記事の目的です。循環配列では、末尾の要素の次が先頭の要素に戻るため、通常の最大部分配列問題（カデーンのアルゴリズム）よりも少し工夫が必要になります。

入出力例

例1

入力： int arr[] = {1, 2, 8, 4, 3, 0, 7}

出力： 最大循環部分配列の合計は 22

解説： 配列 {1, 2, 8, 4, 3, 0, 7} が与えられています。循環を考慮すると、末尾の「7」に先頭の「1」「2」をつなげられるため、7 + 1 + 2 + 8 + 4 = 22 が最大の合計となります。

例2

入力： int arr[] = {2, 5, -1, 6, 9, 4, -5}

出力： 最大循環部分配列の合計は 25

解説： 配列 {2, 5, -1, 6, 9, 4, -5} が与えられています。負の要素「-5」を除外し、4 + 2 + 5 + (-1) + 6 + 9 = 25 が最大の合計となります。

アルゴリズムの考え方

この問題を効率的に解くには、次の2つのケースを考える必要があります。

• ケース1：最大部分配列が配列の途中にある場合 — 通常のカデーンのアルゴリズムで最大合計（temp_2）を求めます。
• ケース2：最大部分配列が配列の両端にまたがる場合 — これは「全体の合計から最小部分配列の合計を引く」ことで求められます。つまり、total − 最小部分配列の合計 が答えになります。

最終的な答えは、この2つのうち大きい方です。ただし、すべての要素が負の場合など、最小部分配列が配列全体と一致するケース（temp_4 == total）は、ケース2が不正な空配列を選んでしまうため、ケース1の結果をそのまま返す必要があります。

手順の詳細

1. 正負両方の値を含む整数型配列を入力として受け取ります。
2. 配列のサイズを計算します。
3. 配列とサイズを関数に渡して処理を行います。
4. 一時変数 total を作成し、0 で初期化します。
5. i を 0 から配列サイズまでループさせ、total に arr[i] を加算していきます（= 配列全体の合計）。
6. temp = temp_2 = temp_3 = temp_4 = arr[0] と初期化します。
7. i を 1 から配列サイズまでループさせ、以下を更新します。
   ・temp = max(temp + arr[i], arr[i]) … 現在位置で終わる最大部分配列の合計
   ・temp_2 = max(temp_2, temp) … 全体の最大部分配列の合計
   ・temp_3 = min(temp_3 + arr[i], arr[i]) … 現在位置で終わる最小部分配列の合計
   ・temp_4 = min(temp_4, temp_3) … 全体の最小部分配列の合計
8. size == 1 の場合は arr[0] を返します。
9. temp_4 == total（全要素が最小部分配列になってしまう場合）なら temp_2 を返します。
10. max_sum = max(temp_2, total − temp_4) を計算して返します。
11. 結果を出力します。

実装例（C++）

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

int maximum(int arr[], int size){
    // 配列全体の合計を計算
    int total = 0;
    for (int i = 0; i < size; i++){
        total += arr[i];
    }

    // カデーンのアルゴリズムで最大・最小部分配列の合計を同時に求める
    int temp   = arr[0]; // 現在位置で終わる最大合計
    int temp_2 = arr[0]; // 最大部分配列の合計
    int temp_3 = arr[0]; // 現在位置で終わる最小合計
    int temp_4 = arr[0]; // 最小部分配列の合計

    for (int i = 1; i < size; i++){
        temp   = max(temp + arr[i], arr[i]);
        temp_2 = max(temp_2, temp);
        temp_3 = min(temp_3 + arr[i], arr[i]);
        temp_4 = min(temp_4, temp_3);
    }

    // 要素が1つだけの場合
    if (size == 1){
        return arr[0];
    }

    // 最小部分配列が全体と一致する場合は循環ケースを採用しない
    if (temp_4 == total){
        return temp_2;
    }

    // 通常の最大と「全体 − 最小部分配列」の大きい方を返す
    int max_sum = max(temp_2, total - temp_4);
    return max_sum;
}

int main(){
    int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum circular subarray sum is: " << maximum(arr, size) << endl;
    return 0;
}

出力結果

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

Maximum circular subarray sum is: 25

まとめ

本アルゴリズムは、カデーンのアルゴリズムを最大・最小の両方向に適用することで、時間計算量 O(n)・空間計算量 O(1) で循環配列の最大部分配列合計を求められます。単純に全パターンを調べる総当たり法（O(n²)）と比べて非常に効率的なので、競技プログラミングやコーディング面接でも頻出のテクニックです。