53. !*最大子序和（动态规划）

<?php
class Solution {
    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 输入: [-2,1,-3,4,-1,2,1,-5,4]
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     *
     *
     *
     * 动态规划：
     *  1. 状态定义：$dp[i] 前i个数（包括i）中的最大连续子数组的和
     *  2. 状态转移方程：$dp[$i] = $dp[$i - 1] < 0 ? $nums[$i] : $dp[$i - 1] + $nums[$i]
     *
     * @param Integer[] $nums
     * @return Integer
     */
    public function maxSubArray($nums) {
        if (!$nums) return 0;
        $max = $dp[0] = $nums[0];
        for ($i = 1; $i < count($nums); $i++) {
            $dp[$i] = $dp[$i - 1] < 0 ? $nums[$i] : $dp[$i - 1] + $nums[$i];
            $max = max($max, $dp[$i]);
        }
        return $max;
    }
}
$nums = [-2,1,-3,4,-1,1,2,1,-5,4,2,1];
$cls = new Solution();
$r = $cls->maxSubArray($nums);
echo $r;