整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。

手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）

あるインデックス i で終了する連続部分配列の最大和を run_sum と定義します。i における値は、直前の run_sum に nums[i] を足した値と、nums[i] 単独の値を比較し、大きい方を選ぶことで決定できます。この性質を利用すれば、配列を1回走査するだけで全体の最大和を導出可能です。履歴配列を使わずに直前値だけを保持することで、メモリ使用量を最小限に抑えます。

class Solution {
    public int maxSubArray(int[] arr) {
        int currentRun = arr[0];
        int globalMax = arr[0];
        for (int i = 1; i < arr.length; i++) {
            currentRun = Math.max(arr[i], currentRun + arr[i]);
            globalMax = Math.max(globalMax, currentRun);
        }
        return globalMax;
    }
}

class Solution:
    def maxSubArray(self, arr: list[int]) -> int:
        current_run = global_max = arr[0]
        for val in arr[1:]:
            current_run = max(val, current_run + val)
            global_max = max(global_max, current_run)
        return global_max

計算量: 時間計算量は O(n) で、配列を1回だけ反復処理します。空間計算量は O(1) で、定数個の変数しか使用しません。

手法2：累積和の差分による最適化

部分配列の和は、ある位置までの累積和からそれより前の累積和を引くことで表せます。つまり、prefix[j] - prefix[i] が最大となる組み合わせを見つける問題に帰着できます。走査中に現在の累積和 cum_val を更新し、同時にこれまでに見た最小の累積和 min_prefix を記録しておきます。各ステップで cum_val - min_prefix の差分を計算し、それがこれまでの最大和を上回れば更新します。

class Solution {
    public int maxSubArray(int[] arr) {
        int cumVal = 0;
        int minPrefix = 0;
        int result = Integer.MIN_VALUE;
        for (int val : arr) {
            cumVal += val;
            result = Math.max(result, cumVal - minPrefix);
            minPrefix = Math.min(minPrefix, cumVal);
        }
        return result;
    }
}

import math
class Solution:
    def maxSubArray(self, arr: list[int]) -> int:
        cum_val = 0
        min_prefix = 0
        result = -math.inf
        for val in arr:
            cum_val += val
            result = max(result, cum_val - min_prefix)
            min_prefix = min(min_prefix, cum_val)
        return result

計算量: 時間計算量は O(n) です。各要素に対して定数時間のみで処理が完了します。空間計算量は O(1) です。

手法3：分割統治法による再帰探索

配列を中央で分割し、左半分、右半分、中央を跨ぐ部分の3つのケースから最大和が得られることを利用します。左右のサブ配列は再帰的に解き、中央を跨ぐケースについては中央要素を起点として左右に伸びる最大和をそれぞれ計算し、合計値を求めます。3つの候補を比較して最大値を返すことで、全体解が得られます。

class Solution {
    public int maxSubArray(int[] arr) {
        return solveDivide(arr, 0, arr.length - 1);
    }

    private int solveDivide(int[] arr, int left, int right) {
        if (left == right) return arr[left];
        int mid = left + (right - left) / 2;
        int leftMax = solveDivide(arr, left, mid);
        int rightMax = solveDivide(arr, mid + 1, right);
        int crossMax = computeCross(arr, left, mid, right);
        return Math.max(leftMax, Math.max(rightMax, crossMax));
    }

    private int computeCross(int[] arr, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int tempSum = 0;
        for (int i = mid; i >= left; i--) {
            tempSum += arr[i];
            leftSum = Math.max(leftSum, tempSum);
        }

        int rightSum = Integer.MIN_VALUE;
        tempSum = 0;
        for (int i = mid + 1; i <= right; i++) {
            tempSum += arr[i];
            rightSum = Math.max(rightSum, tempSum);
        }
        return leftSum + rightSum;
    }
}

import math
class Solution:
    def maxSubArray(self, arr: list[int]) -> int:
        def split_search(l: int, r: int) -> int:
            if l == r:
                return arr[l]
            m = l + (r - l) // 2
            l_max = split_search(l, m)
            r_max = split_search(m + 1, r)
            
            curr = 0
            left_peak = -math.inf
            for i in range(m, l - 1, -1):
                curr += arr[i]
                left_peak = max(left_peak, curr)
                
            curr = 0
            right_peak = -math.inf
            for i in range(m + 1, r + 1):
                curr += arr[i]
                right_peak = max(right_peak, curr)
                
            return max(l_max, r_max, left_peak + right_peak)
            
        return split_search(0, len(arr) - 1)

計算量: 時間計算量は O(n log n) です。配列を二分する再帰の深さが log n であり、各段階で線形時間で部分解を計算するためです。空間計算量は O(log n) で、再帰呼び出しスタックの深さに比例します。