連続部分配列の最大和を求めるJava

動的計画法を使用して、配列の連続した部分配列の最大和を求める。

配列 nums が与えられたら、変数 sum を用いて現在の連続部分配列の合計を表す。初期値は 0 に設定する。また、変数 maxSum を用いて最大の合計を表す。初期値は配列の最初の要素に設定する。

配列を走査し、配列の各要素 num について以下を実行します。

1. 0以上のsumは、先行する連続部分配列の和が、後続部分配列に寄与していることを示し、numをsumに加算し、maxSumを更新する。
2. 負ならその前の連続部分列の和が後ろの部分列の和に寄与しないことを表すので、sumをnumで更新する。
3. sumとmaxSumの値を比較し、大きい方をmaxSumに代入する。

よって、maxSumが連続部分配列の最大の合計になります。

以下のようなJavaコードを使って実装できます：

public int maxSubArray(int[] nums) {
    int sum = 0;
    int maxSum = nums[0];
    
    for (int num : nums) {
        if (sum >= 0) {
            sum += num;
        } else {
            sum = num;
        }
        
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum;
}

O(n)の時間計算量で連続部分列の最大和を求めることができる手法