PHP求最大子序列和的算法实现

yipeiwu_com5年前PHP代码库
复制代码 代码如下:

<?php
//作者:遥远的期待
//QQ:15624575
//算法分析:1、必须是整数序列、2、如果整个序列不全是负数,最大子序列的第一项必须是正数,否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;3、如果整个序列都是负数,那么最大子序列的和是0;
//全负数序列很简单,不举例
$arr=array(4,-3,5,-2,-1,2,6,-2);
function getmaxsum($arr){
$thissum=0;
$maxsum=0;
$start=0;//记录子序列的起始下标
$end=0;//记录子序列的结束下标
for($i=0;$i<count($arr);$i++){
$thissum+=$arr[$i];//取得当前子序列的和
if($thissum>$maxsum){//如果当前子序列的和大于当前最大子序列的和
$maxsum=$thissum;//改变当前最大子序列的和
$end=$i;
}else if($thissum<0){//如果当前子序列的和小于0,则把下一个元素值假定为最大子序列的第一项,这里可以保证最大自序列的第一项一定是正数
$thissum=0;//前提这个序列不全是负数
$start=$i+1;
}
}
$parr=array($start,$end,$maxsum);
return $parr;
}
list($start,$end,$maxsum)=getmaxsum($arr);
echo '最大子序列是:';
for($i=$start;$i<=$end;$i++){
echo $arr[$i].' ';
}
echo '<br>';
echo '最大子序列的和是'.$maxsum;
?>

相关文章

php产生随机数的两种方法实例代码 输出随机IP

分享下php生成随机数的三种方法,生成1-10之间的不重复随机数,php生成不重复随机数的例子,需要的朋友参考下。 如何用php生成1-10之间的不重复随机数? 例1,使用shuffle...

PHP实现的防止跨站和xss攻击代码【来自阿里云】

本文实例讲述了PHP实现的防止跨站和xss攻击代码。分享给大家供大家参考,具体如下: 文档说明: 1.将waf.php传到要包含的文件的目录 2.在页面中加入防护,有两种做法,根据情况二...

php简单检测404页面的方法示例

php简单检测404页面的方法示例

本文实例讲述了php简单检测404页面的方法。分享给大家供大家参考,具体如下: 需求描述: 检测给定的url是否是404页面。 方式一: 使用file_get_contents函数,可以...

php mb_substr()函数截取中文字符串应用示例

substr()函数用来截取字符串,但是对于中文字符会出现问题,而mb_substr()和mb_strcut这两个函数可以,用法与substr()相似,只是在函数最后要加入多一个参数,以...

PHP模拟asp中response类实现方法

本文实例讲述了PHP模拟asp中response类的方法。分享给大家供大家参考。具体如下: 习惯了asp或是asp.net开发的人, 他们会经常用到response类,这个类用于处理客户...