<?php 
/**
 * 连续子数组的最大和
 * 输入一个整形数组，数组有正数有负数，数组的一个或多个整数组成一个子数组，求所有的子数组的和的最大值，要求时间复杂度为O(n)
 *
 * 动态规划
 * F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
   F（i）=max（F（i-1）+array[i] ， array[i]）
 */

function FindGreatestSumOfSubArray($array)
{
	if (!is_array($array) || empty($array)) {
		exit('参数错误');
	}
    $curSum = 0; // 当前和
    $maxSum = 0; // 历史的最大值
    foreach ($array as $key => $value) {
    	if ($curSum < 0) {     // 如果前子数组的和小于0，那么加上后面的一个值，仍然会减小， 1,-2,3 在1,-2中和为-1，再加3，和为2，此时2比3小
    	//所以只要前面的和是负数，加上当前数的和，一定比当前的数要小，所以舍弃前面的和，将当前的值，设置为当前的和
    		$curSum = $value;   
    	} else {   // 前面的和为正数则，相加
    		$curSum += $value;
    	}

    	if ($curSum > $maxSum) {  // 与历史的最大值比较，更新最大值
    		$maxSum = $curSum;
    	}
    }
    return $maxSum;
}

$array = [1, -2, 3, 10, -4, 7, 2, -5];
var_dump(FindGreatestSumOfSubArray($array));