PHP求最大子序列和的算法实现
时间:2023-11-15 04:17:28
<?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;
?>
标签:最大子序列
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
PHP5中新增stdClass 内部保留类
2024-05-09 14:47:55
python方法如何实现字符串反转
2022-10-26 22:07:03
![](https://img.aspxhome.com/file/2023/5/76175_0s.png)
Python SQLite3简介
2023-05-29 11:26:01
mac 上配置Pycharm连接远程服务器并实现使用远程服务器Python解释器的方法
2021-10-19 18:40:40
![](https://img.aspxhome.com/file/2023/8/127318_0s.png)
python进行参数传递的方法
2023-05-21 06:15:32
python实现将一个数组逆序输出的方法
2022-07-16 11:07:51
mysql-joins具体用法说明
2024-01-19 10:32:19
![](https://img.aspxhome.com/file/2023/3/118153_0s.png)
php编程每天必学之表单验证
2023-07-19 05:50:59
python 如何通过KNN来填充缺失值
2022-09-28 10:39:16
![](https://img.aspxhome.com/file/2023/7/105247_0s.png)
Python3网络爬虫开发实战之极验滑动验证码的识别
2022-10-02 22:06:14
![](https://img.aspxhome.com/file/2023/1/85221_0s.jpg)
解决django model修改添加字段报错的问题
2021-06-18 12:06:38
![](https://img.aspxhome.com/file/2023/6/131436_0s.jpg)
pytorch 实现计算 kl散度 F.kl_div()
2023-04-03 20:16:18
![](https://img.aspxhome.com/file/2023/1/101591_0s.png)
Python 50行爬虫抓取并处理图灵书目过程详解
2023-09-01 22:35:49
Python和Go成为2019年最受欢迎的黑客工具(推荐)
2021-05-22 16:37:17
![](https://img.aspxhome.com/file/2023/8/131898_0s.png)
基于spring boot 日志(logback)报错的解决方式
2022-05-12 08:13:46
浅谈Python中用datetime包进行对时间的一些操作
2022-09-27 09:32:14
深入理解JavaScript系列(28):设计模式之工厂模式详解
2024-05-06 10:08:17
PHP 解决utf-8和gb2312编码转换问题
2024-04-29 13:56:45
在linux下实现 python 监控usb设备信号
2022-04-18 15:29:24
Numpy中的mask的使用
2022-06-10 19:33:11
![](https://img.aspxhome.com/file/2023/2/87572_0s.jpg)