PHP求最大子序列和的算法实现
更新时间：2011年06月24日 22:23:44 作者：
给定整数：A1 A2 A3 A4 … An,其中可能有负数，求Ai-Aj的和的最大值。
（福利推荐：【腾讯云】服务器最新限时优惠活动，云服务器1核2G仅99元/年、2核4G仅768元/3年，立即抢购>>>：9i0i.cn/qcloud）
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
复制代码 代码如下:
<?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;
?>
相关文章
continue跳转语句用来跳过本次循环中指定条件的语句，并且继续执行其他的循环语句。下面这篇文章主要给大家介绍了关于在PHP中用continue跳过本次循环中剩余代码的一个注意点，文中的内容比较基础，需要的朋友可以参考借鉴，下面来一起看看吧。2017-06-06
/etc/php-fpm.d/www.conf 配置注意事项
下面小编就为大家带来一篇/etc/php-fpm.d/www.conf 配置注意事项。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧2017-02-02
运行安装文件（ZendServer-CE-php-5.3.2-5.0.1-Windows_x86.exe）开始安装，选项请参照我的选择。2010-04-04
本文给大家分享的是PHP中SESSION的注销与清除的方法和示例，非常的实用，有需要的小伙伴可以参考下。2015-04-04
我想博客中的 文章列表和单个的文章阅读 统一起来，我觉得除了sql查询语句结构不同，HTML代码不同，其它也就一样。不过话说回来，这两个都是主要功能，所以这的确有点不适合，不过昨晚读了一点设计模式，好歹得写点啥好。2011-09-09
这篇文章主要介绍了php类常量用法,实例分析了php中类常量的概念、特性与相关使用技巧,需要的朋友可以参考下2015-07-07
php中DOMDocument简单用法示例代码(XML创建、添加、删除、修改)
PHP写XML方法很多，这里主要介绍一下DOMDocument的用法，跟 JS大体上相同，其实非常简单。2010-12-12
这篇文章主要介绍了PHP安全下载文件的方法,涉及PHP文件的编码设置,转换,判断及下载的相关技巧,需要的朋友可以参考下2016-04-04
这款软件的功能就是通过在内存中缓存PHP文件从而加速PHP程序的执行速度。由于MMCache的原作者被Zend挖走，MMCache的开发一直处于停滞状态。而Eaccelerator却借鉴了MMCache的优点而一直在不断的更新。2008-10-10
在手册中遇到了一个没想明白的问题，记录一下，方便需要的朋友2012-11-11
最新评论