53. 最大子序和

题意：

解题思路：

思路：
DP两部曲 
1.状态定义：dp[i]: 到i下标的时候连续的最大和
2.状态转移方程：如果dp[i] = if 如果dp[i - 1]是负数，那么dp[i] = nums[$i]
   else dp[i] = dp[i - 1] + nums[i]

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
        return $this->maxSubArrayDP($nums);
        $sum = 0;
        $ans = $nums[0];
        foreach ($nums as $num) {
            $sum = $sum > 0 ? ($sum += $num) : $num;
            $ans = max($ans, $sum);
        }
        return $ans;
    }
    function maxSubArrayDP($nums) {
        if (!$nums) return 0;
        $dp = [];
        $dp[0] = $nums[0];
        $max = $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;
    }
    function maxSubArrayForce($nums) {
        $max = PHP_INT_MIN;
        for ($i = 0; $i < count($nums); $i++) {
            $sum = 0;
            for ($j = $i; $j < count($nums); $j++) {
                $sum += $nums[$j];
                if ($sum > $max) $max = $sum;
            }
        }
        return $max;
    }
}

GO代码实现：

func maxSubArray(nums []int) int {
    maxNum := nums[0]
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        maxNum = max(maxNum, dp[i])
    }
    return maxNum
}
func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

func maxSubArray(nums []int) int {
    l := len(nums)
    max := nums[0]
    for i:=1; i<l; i++ {
        if nums[i-1] >  0 {
            nums[i] += nums[i-1]
        }
        if nums[i] > max {
            max = nums[i]
        }
    }
    return max
}