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 模拟$_PUT实现代码

PHP里有$_GET,$_POST,但是没有$_PUT,所以如果需要使用它的话,则你不得不自己模拟一下: 复制代码 代码如下: $_PUT = array(); if ('PUT' ==...

php通过function_exists检测函数是否存在的方法

本文实例讲述了php通过function_exists检测函数是否存在的方法。分享给大家供大家参考。具体分析如下: php中可以通过function_exists()函数检测另外一个函数...

php设计模式 Composite (组合模式)

复制代码 代码如下: <?php  /**  * 组合模式  *  * 将对象组合成树形结构以表示"部分-整体"的层次结构,使得客户对单个对...

PHP自带ZIP压缩、解压缩类ZipArchiv使用指南

要使用该PHP扩展类,需要(PHP 5 >= 5.2.0, PECL zip >= 1.1.0),部分方法需要 PHP 5.2.+,且php.ini配置支持zip 对于wi...

php str_pad 函数用法简介

语法 str_pad(string,length,pad_string,pad_type) 参数 描述 string 必需。规定要填充的字符串。 length 必需。规定新字符串的长度。...