Case description:
Write a PHP function. To find the largest continuous sum among any n positive and negative integers, the time complexity of the algorithm is required to be as low as possible;
For example: echo getMaxSum(array(-2, 1, 3, 9, -4, 2, 3, 5, - 3,-4,1,3));//The maximum continuous sum is (1,3,9,-4,2,3,5) The addition function returns 19
The code is as follows:
//算法分析：
//1、必须是整数序列
//2、如果整个序列不全是负数，最大子序列的第一项必须是正数，
//否则最大子序列后面的数加起来再加上第一项的负数，其和肯定不是最大的；
//3、如果整个序列都是负数，那么最大子序列的和是0；
//全负数序列很简单，不举例
$arr=array(-2,1,3,9,-4,2,3,5,-3,-4,1,3);
$thissum=0;
$maxsum=0;
$start=0;//记录子序列的起始下标
$end=0;//记录子序列的结束下标
for($i=0;$i$maxsum){//如果当前子序列的和大于当前最大子序列的和
$maxsum=$thissum;//改变当前最大子序列的和
$end=$i;
}else if($thissum<0){//如果当前子序列的和小于0，则把下一个元素值假定为最大子序列的第一项,这里可以保证最大自序列的第一项一定是正数
$thissum=0;//前提这个序列不全是负数
$start=$i+1;
}
}
$parr=array($start,$end,$maxsum);
list($start,$end,$maxsum)=$parr;
print_r($arr);
echo '最大子序列是:';
for($i=$start;$i<=$end;$i++){
echo $arr[$i].' ';
}
echo '
';
echo '最大子序列的和是'.$maxsum;
?>
Effect as follows:
Array
(
[0] => -2
[1] => 1
[2] => 3
[3] => 9
[4] => -4
[5] => 2
[6] => 3
[7] => 5
[8] => -3
[9] => -4
[10] => 1
[11] => 3
)
最大子序列是:1 3 9 -4 2 3 5
最大子序列的和是19
This completes the requirements of the case, the idea is very important!
The above introduces the difference between direct free kick and indirect free kick. PHP finds the largest continuous sum among any n positive and negative integers, including the difference between direct free kick and indirect free kick. I hope friends are interested in PHP tutorials. Helps.
