直接任意球和间接任意球的区别 PHP 求任意n个正负整数里面最大的连续和
程序员文章站
2022-05-01 16:29:42
...
案例描述:
编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低;
例如:echo getMaxSum(array(-2,1,3,9,-4,2,3,5,-3,-4,1,3));//最大连续和是(1,3,9,-4,2,3,5)相加函数返回19
代码如下:
//算法分析: //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'; echo '最大子序列的和是'.$maxsum; ?>
效果如下: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
这样就完成了案例的要求,思路很重要!以上就介绍了直接任意球和间接任意球的区别 PHP 求任意n个正负整数里面最大的连续和,包括了直接任意球和间接任意球的区别方面的内容,希望对PHP教程有兴趣的朋友有所帮助。