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

yipeiwu_com6年前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的autoload机制的实现解析

一、autoload机制概述 在使用PHP的OO模式开发系统时,通常大家习惯上将每个类的实现都存放在一个单独的文件里,这样会很容易实现对类进行复用,同时将来维护时也很便利。这也是OO设计...

PHP+ajax实现获取新闻数据简单示例

PHP+ajax实现获取新闻数据简单示例

本文实例讲述了PHP+ajax实现获取新闻数据的方法。分享给大家供大家参考,具体如下: Get方式获取到的信息是字符串(responseText) ① 可以借助JSON对象的方法:str...

[PHP]实用函数8

//建立dBase资料表 int dBase_create(string filename,array fields) //打开dBase资料表 int&n...

通过具体程序来理解PHP里面的抽象类

当然,可能存在多个根类,用来实现不同的功能. 在一个良好设计的体系中,每个根类都应该有一个有用的接口, 可以被应用代码所使用. 如果我们的应用代码被设计成与根类一起工作,那么它也可以和任...

详解WordPress开发中get_header()获取头部函数的用法

函数意义详解 从当前主题调用header.php文件。是不是很简单?好吧,如果你是新手的话这里要提醒一下,这里的get和get_children()、get_category中的get略...