假设以第i个元素结尾的最大连续子串的和为sum[i]，则以第i+1个元素结尾的最大连续子串的和，要么为sum[i]+a[i+1]，要么为a[i+1]，也即sum[i+1] = max{sum[i]+ a[i+1],a[i+1]}，也即：当sum[i]>0时：sum[i+1] = sum[i]+ a[i+1]，当sum[i]<0时，sum[i+1] = a[i+1];
这是典型的动态规划。其实很清晰很简单，但网上有些帖子讲的很绕很复杂。导致我跪了。。。
本题重点就在于：假设了以第i个元素结尾的最长子串的和为sum[i]，并且理清了以第i+1个元素结尾的最长子串的和sum[i+1]与以第i个原酸结尾的最长子串的和sum[i]的关系 。
//求任意n个正负整数里面最大的连续和
$arr = [-10, -9, 8, -4, -2, 0, 1, -2, 3, 4, -5, 6, 9];
function max_sum_array($arr)
{
$currSum = 0;
$maxSum = 0;//数组元素全为负的情况，返回最大数
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
if ($currSum >= 0) {
$currSum += $arr[$i];
} else {
$currSum = $arr[$i];
}
}
if ($currSum > $maxSum) {
$maxSum = $currSum;
}
return $maxSum;
}
var_dump(max_sum_array($arr));
