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

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

WBOY
WBOY原创
2016-07-28 08:27:461382浏览

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教程有兴趣的朋友有所帮助。

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn