编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。

php中文网
发布: 2016-07-28 08:27:46
原创
1510人浏览过

header("content-type:text/html;charset=utf8");
//算法分析:
//1、必须是整数序列
//2、如果整个序列不全是负数,最大子序列的第一项必须是正数,
//否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;
//3、如果整个序列都是负数,那么最大子序列的和是0;
    $arr=array(-2,1,3,9,-4,2,3,8,-3,-4,1,3);
        $thissum=0;
        $maxsum=0;
        $start=0;//记录子序列的起始下标
        $end=0;//记录子序列的结束下标
        for($i=0;$i            $thissum+=$arr[$i];//取得当前子序列的和
            if($thissum>$maxsum){//如果当前子序列的和大于当前最大子序列的和
                $maxsum=$thissum;//改变当前最大子序列的和
                $end=$i;
            }else if($thissum                $thissum=0;//前提这个序列不全是负数
                $start=$i+1;
            }
        }
        $parr=array($start,$end,$maxsum);
    list($start,$end,$maxsum)=$parr;
    print_r($arr);
    echo '
';
    echo '最大子序列是:';
    for($i=$start;$i        echo $arr[$i].' ';
    }
    echo '
';
    echo '最大子序列的和是'.$maxsum;
?>

以上就介绍了 编写一个PHP函数。求任意n个正负整数里面最大的连续和,要求算法时间复杂度尽可能低。,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号