题目链接：53.最大子序和
题目描述
难度 简单 描述 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
示例 2： 输入：nums = [1] 输出：1
示例 3： 输入：nums = [0] 输出：0
示例 4： 输入：nums = [-1] 输出：-1
示例 5： 输入：nums = [-100000] 输出：-100000
提示： 1 <= nums.length <= 3 * 104 -105 <= nums[i] <= 105
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
自行解法
一开始并没有想到合适的解法，于是想到最暴力的方式，获取所有子序和并比较
class Solution {
/**
* 出所有的子序和之后进行比较
* @param Integer[] $nums
* @return Integer
*/
function maxSubArray($nums) {
$maxForI = [];
for ($i = 0; $i < count($nums); $i++) {
$sumForI = $nums[$i];
$maxForJ = [];
$max = max($nums);
for ($j = $i + 1; $j < count($nums); $j++) {
if ($i == $j) {
$sumForI = $nums[$i];
} else {
$sumForI += $nums[$j];
}
$maxForJ[] = max($maxNum, $sumForI, $max);
$maxNum = $sumForI;
}
if (count($nums) == 1) {
$maxForJ = $nums;
}
$maxForI[$i] = max($maxForJ);
}
return max($maxForI);
}
}
这种方式可以通过绝大部分测试用例，但是当$nums增加到一定数量级后会超时
其他解法
经过查阅资料，发现这里会有更好的解法
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function maxSubArray($nums) {
$res = $nums[0];
$sum = 0;
foreach ($nums as $num) {
if ($sum > 0) {
$sum += $num;
} else {
$sum = $num;
}
$res = max($res, $sum);
}
return $res;
}
}