LeetCode 53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

数列が与えられ、合計が最大値となる部分配列を返す、という問題。
恥ずかしながら当初解法がわからなかったが、最大部分配列問題:カダネのアルゴリズムとセットでよく使われるようだ。
覚えておこう。

基本的には数列を最初から一つずつ走査していく。そのため計算量としてはO(n)となる。

1. 部分配列の和の最大値を記録する変数MAXを用意する。初期値は数列の最初の値。
2. 配列のカーソル位置の値と、一つ前の値を足し合わせる。（カーソルは数列の2番めから始める）
3. その計算結果と、カーソル位置の値とを比較し、大きいものを現在のカーソル位置に書き込む。
4. 更に、現在のカーソル位置の値とMAXを比較し、大きい方をMAXに書き込む。
5. カーソルが数列の末尾に到達するまで2〜4を繰り返す。

下記に具体例をもとに実際の処理の流れを示す。

class Solution {

    /**
     * @param int[] $nums
     * @return int
     */
    function maxSubArray($nums) {
        $max = $nums[0];
        for ($i=1; $i<count($nums); $i++) {
            $nums[$i] = max($nums[$i-1]+$nums[$i], $nums[$i]);
            $max = max($max, $nums[$i]);
        }
        return $max;
    }
}