Rumah > pembangunan bahagian belakang > tutorial php > 直接任意球和间接任意球的区别 PHP 求任意n个正负整数里面最大的连续和

直接任意球和间接任意球的区别 PHP 求任意n个正负整数里面最大的连续和

WBOY
Lepaskan: 2016-07-28 08:29:55
asal
986 orang telah melayarinya

案例描述:

编写一个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

代码如下:

<?php header(&#39;content-type:text/html;charset=utf8 &#39;);
Salin selepas log masuk
//算法分析:
//1、必须是整数序列
//2、如果整个序列不全是负数,最大子序列的第一项必须是正数,
//否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;
//3、如果整个序列都是负数,那么最大子序列的和是0;
<pre name="code" class="html">//全负数序列很简单,不举例
	$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<count if>$maxsum){//如果当前子序列的和大于当前最大子序列的和
				$maxsum=$thissum;//改变当前最大子序列的和
				$end=$i;
			}else if($thissum';
	echo '最大子序列的和是'.$maxsum;
 ?></count>
Salin selepas log masuk


效果如下:

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 <br>最大子序列的和是19
Salin selepas log masuk

这样就完成了案例的要求,思路很重要!

以上就介绍了直接任意球和间接任意球的区别 PHP 求任意n个正负整数里面最大的连续和,包括了直接任意球和间接任意球的区别方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan