KadaneのアルゴリズムをC++で実装する方法【最大部分配列和の求め方】

Kadane（カダネ）のアルゴリズムは、整数配列の中から連続する部分配列の合計が最大になる組み合わせを効率よく見つけるための手法です。本記事では、その基本的な考え方と、C++による実装例、実行結果について詳しく解説します。

Kadaneのアルゴリズムとは

負の数を含む整数配列が与えられたとき、合計値が最大となる連続した部分配列を探す問題は「最大部分配列和問題」と呼ばれます。すべての部分配列を総当たりで調べるとO(n²)〜O(n³)の時間がかかりますが、Kadaneのアルゴリズムを使えばたった1回の走査（O(n)）で答えを求められます。

基本的な考え方はシンプルで、各要素に対して次のどちらか大きい方を選びながら配列を走査します。

• 現在までの部分配列に要素を付け足す（currentElementMax + array[i]）
• その要素から新しい部分配列を始める（array[i]）

そして、走査の途中で現れた最大値をhighestMaxとして常に記録しておきます。

アルゴリズムの手順

Begin
Function kadanes(int array[], int length):
    Initialize
    highestMax = 0
    currentElementMax = 0
    for i = 0 to length-1
        currentElementMax = max(array[i], currentElementMax + array[i])
        highestMax = max(highestMax, currentElementMax)
    return highestMax
End

C++での実装例

#include<iostream>
using namespace std;

int kadanes(int array[], int length) {
    int highestMax = 0;
    int currentElementMax = 0;
    for (int i = 0; i < length; i++) {
        currentElementMax = max(array[i], currentElementMax + array[i]);
        highestMax = max(highestMax, currentElementMax);
    }
    return highestMax;
}

int main() {
    cout << "Enter the array length: ";
    int l;
    cin >> l;
    int arr[l];
    cout << "Enter the elements of array: ";
    for (int i = 0; i < l; i++) {
        cin >> arr[i];
    }
    cout << "The Maximum Sum is: " << kadanes(arr, l) << endl;
    return 0;
}

実行結果

Enter the array length: 7
Enter the elements of array:
-1
-2
-3
-4
-5
6
7
The Maximum Sum is: 13

この例では、配列 {-1, -2, -3, -4, -5, 6, 7} の中で、末尾の「6 + 7 = 13」という部分配列が最大の合計となります。

計算量と注意点

• 時間計算量：O(n)（配列を1回だけ走査）
• 空間計算量：O(1)（追加の配列が不要）

なお、上記の実装では初期値が0のため、すべての要素が負の配列を入力すると結果は必ず0になります。すべて負のケースでも正しい値（負の数の中で最大のもの）を返したい場合は、highestMaxとcurrentElementMaxの初期値をarray[0]に設定し、ループを i = 1 から開始するよう変更してください。