最大部分配列問題

この記事では、最大部分配列問題の様々な解法について説明します。より詳細なアルゴリズムの考え方は「アルゴリズムイントロダクション」を参照してください。

部分配列構造体

typedef struct {
    int start, end, total;
} SubArray;

力まかせ法による解法

すべての配列区間の和を計算して最大部分配列を見つける方法です。アルゴリズムの複雑さはθ(n²)です。小規模データでは良好なパフォーマンスを示しますが、大規模データでは非効率です。ただし、分割統治法の改良に利用できます。実装の考え方は、まずiを開始点とする最大部分配列を計算し、その後[1..n], [2..n] .. [n..n]の中から最大の部分配列を見つけることです。

SubArray MaxSubArray_BruteForce(int start, int end, int arr[]) {
    int sum;
    int max_index = 0;
    SubArray *S = (SubArray *)calloc((end - start + 2), sizeof(SubArray));

    for (int i = start, k = 0; i <= end; ++i, ++k) {
        S[k].total = INT_MIN;
        S[k].start = i;
        sum = 0;
        for (int j = i; j <= end; ++j) {
            sum += arr[j];
            if (S[k].total < sum) {
                S[k].total = sum;
                S[k].end = j;
            }
        }
        if (S[max_index].total <= S[k].total)
            max_index = i - start;
    }

    return S[max_index];
}

分割統治法による解法

分割統治法の時間分析から、

もし[low..high]の最大部分配列を探す場合、分割統治法の技術は配列をできるだけ等しい大きさの2つの部分配列に分割することを意味します（a=2）。中間位置midを見つけ、次に部分配列[low..mid]と[mid+1..high]を解きます。配列[low..high]の最大部分配列[i..j]は必ず以下の3つのケースのいずれかになります： - 部分配列[low..mid]に完全に含まれるため、`low <= i <= high <= mid` - 部分配列[mid+1..high]に完全に含まれるため、`mid+1 <= i <= j <= high` - 中間点midをまたぐため、`low <= i <= mid <= j <= high` また、中間点midをまたぐ配列は**必ずmidとmid+1を含まなければなりません**。

再帰的に部分配列[low..mid]と[mid+1..high]を解き、部分問題の规模を縮小します。最後に中間点をまたぐ最大部分配列を見つけます。マージソートのマージプロセスと似ていますが、中間点をまたぐ最大部分配列を見つけることを部分問題のマージプロセスとします。簡単なロジックは以下の通りです：

1. 部分配列[low..mid]の最大部分配列を見つける
2. 部分配列[mid+1..high]の最大部分配列を見つける
3. [low..mid mid+1..high]の最大部分配列を見つける
4. 3つの最大部分配列の中から最大の部分配列を返す。注：ここでの比較には等号を含める必要があり、これにより0をスキップして最大部分配列をより正確に求めることができます

SubArray MaxCrossSubArray(int start, int mid, int end, int arr[]) {
    int left_sum, right_sum, sum;
    SubArray S;

    left_sum = right_sum = INT_MIN;
    sum = 0;
    for (int i = mid; i >= start; i--) {
        sum += arr[i];
        if (left_sum < sum) {
            S.start = i;
            left_sum = sum;
        }
    }
            
    sum = 0;
    for (int j = mid + 1; j <= end; j++) {
        sum += arr[j];
        if (right_sum < sum) {
            S.end = j;
            right_sum = sum;
        }
    }
            
    S.total = left_sum + right_sum;
    return S;
}

SubArray MaxSubArray_DivideConquer(int start, int end, int arr[]) {
    if (start == end) {
        SubArray S;
        S.start = start;
        S.end = end;
        S.total = arr[start];
        return S;
    }

    int mid = (start + end) / 2;
    SubArray left = MaxSubArray_DivideConquer(start, mid, arr);
    SubArray right = MaxSubArray_DivideConquer(mid + 1, end, arr);
    SubArray middle = MaxCrossSubArray(start, mid, end, arr);
    return Max3(left, right, middle);
}

改良された再帰アルゴリズム

前述のように、力まかせ法は大規模データでは非常に非効率ですが、小規模データでは優れたパフォーマンスを発揮します。部分問題の规模が特定の値`n`より小さい場合、力まかせ法を使用して解きます。

// 力まかせ法と分割統治法は40前後で性能が交差する
// 规模が10前後では、力まかせ法が分割統治法を大幅に上回る
SubArray MaxSubArray_Hybrid(int start, int end, int arr[]) {
    if (end - start < 10)
        return MaxSubArray_BruteForce(start, end, arr);
    int mid = (start + end) / 2;
    SubArray left = MaxSubArray_Hybrid(start, mid, arr);
    SubArray right = MaxSubArray_Hybrid(mid + 1, end, arr);
    SubArray middle = MaxCrossSubArray(start, mid, end, arr);
    return Max3(left, right, middle);
}

線形時間アルゴリズム

既知の[1..j]の最大部分配列から[1..j+1]の最大部分配列を計算する考え方：[1..j+1]の最大部分配列は、[1..j]の最大部分配列か、ある部分配列[i..j+1] (1 <= i <= j+1) のいずれかです。具体的な実装は以下の通りです。

SubArray MaxSubArray_Linear(int start, int end, int arr[]) {
    SubArray S = {-1, -1, INT_MIN};
    int sum = 0;
    int current_start = -1;
    for (int i = start; i <= end; ++i) {
        if (sum > 0) {
            sum += arr[i];
        } else {
            sum = arr[i];
            current_start = i;
        }

        if (sum > S.total) {
            S.start = current_start;
            S.end = i;
            S.total = sum;
        }
    }
    return S;
}

コーディング中に遭遇した問題

• 最初の再帰実装ではSubArrayポインタもありましたが、メモリ内の実際のSubArrayは1つしかなく、SubArray変数の計算ごとに値が変わっていました。部分配列のインデックスと合計だけが必要なので、関数内で直接定義し、関数終了時にスタックメモリが回収されるようにしました。
• 力まかせ法の初期のiはすべて0から始まります。単純に呼び出すだけなら問題ありませんが、再帰アルゴリズムが小規模な部分を呼び出す場合、セグメンテーションフォルト（境界外アクセス）が発生します。
• 最大部分配列のサイズは同じですが、アルゴリズムによってインデックスが異なる場合があります。この問題は0をフィルタリングしなかったためです。例えば線形アルゴリズムではif (sum > 0)とすべきで、if (sum >= 0)とすべきではありません。再帰アルゴリズムのMax3で最大部分配列を比較する際には等号を含める必要があります。もう一つのケースは{1, 1, -2, 1, 1}のような場合で、これらのアルゴリズムは[0-1]と[3-4]の2つの答えを返します。この問題はまだ解決していません。

4つのアルゴリズムの時間複雑さ

10万件（なぜもっと大きな数ではないかというと、力まかせ法が遅すぎるため）を処理した場合、4つのアルゴリズムの時間は以下のようになります：

• 力まかせ法：15.12秒
• 単純な再帰アルゴリズム：0.15秒
• 最適化された再帰アルゴリズム：0.12秒
• 線形アルゴリズム：無視できるほどの0.003秒