PHP算法求最大子序列的和

今天高海波就群里学生提出的问题总结了这道题目
给定整数：A1 A2 A3 A4 … An,其中可能有负数，求Ai-Aj的和的最大值。
—————
PHP算法博大精深 一般学习php的人 不太重视这些php算法 但是我要告诉你的是 php算法是php程序员必有的职业“素质” 比如你要应聘大型公司如新浪 腾讯 网易 或一些中小型网络公司 他们面试题目 绝不会少了php算法 因为php算法能反应一个程序员知识的牢固和逻辑思维！所以高海波 php技术博客 建议大家还是要重视php算法！好了 说了这么多 现在正式进入php算法解答这道题目！

<?php//作者：高海波//主页：http://www.it165.net///算法分析：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;?>

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。