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之autoload运行机制实例分析

本文较为深入的分析了PHP的autoload运行机制。对于深入理解PHP运行原理有一定的帮助作用。具体分析如下: php实现autoload有两种方法: 1、拦截器__autoload(...

php通过文件头检测文件类型通用代码类(zip,rar等)

php通过文件头检测文件类型通用代码类(zip,rar等)

有时候我们这样做还不完善。可能有些人上存一些文件,但是他通过修改扩展名,让在我们的文件类型之内。 单实际访问时候又不能展示(因为扩展名与文件内容不符)。下面这个php类,可能能够给我们带...

优化WordPress中文章与评论的时间显示

很多博客都喜欢用 评论发表于 “XXX 分钟 之前”、文章发表于 “XXX 分钟 之前”来显示文章评论的时间,改善的时间显示方式不仅能很直观的告诉读者这篇文章或评论发表距今已有多长时间,...

在PHP中读取和写入WORD文档的代码

复制代码 代码如下:<?  // 建立一个指向新COM组件的索引  $word = new COM(”word.appl...

php的ajax框架xajax入门与试用介绍

一、xajax与其它ajax框架的比较 xajax功能很简单,但很灵活!~它不象其它一些大的框架,功能确实强大,但执行速度不敢恭维。。功能虽多,但不够灵活。api多,学起来简直如同学习一...