php实现最大自序和算法

2021-05-07 22:29

阅读：596

标签：开始元素包含结束 sub function 实现序列子序列

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6（最大子序列:4 -1 2 1 ）

第一种：

$arr =  [-2,1,-3,4,-1,2,1,-5,4];

   function maxSubArray($nums) {
        for($i=1;$i)
            $nums[$i] = max($nums[$i],$nums[$i]+$nums[$i-1]);
        return max($nums);
    }

echo maxSubArray($a);

第二种：

$arr =  [-2,1,-3,4,-1,2,1,-5,4];
$len = count($arr);
$b =[];
$b[0] = $arr[0];
$max = $arr[0] >0 ?$arr[0]:0;
$start_x = 0;
for($i=1;$i)
{
    if(($b[$i-1] + $arr[$i]) > $arr[$i]){
        $b[$i] = $b[$i-1] + $arr[$i];
    }else{
        $b[$i] = $arr[$i];
        $start_x = $i; ;
    }    
    if($max  $b[$i]) {    
        $max = $b[$i];    
        $end_x = $i;
    }
}
print ‘最大子和: ‘.$max."\n";
print ‘开始位置: ‘.$start_x."\t";
print ‘结束位置: ‘.$end_x."\n";
print ‘最大子序列:‘;
for($i=$start_x;$i){
    print $arr[$i].‘ ‘;
}

php实现最大自序和算法

标签：开始元素包含结束 sub function 实现序列子序列

原文地址：https://www.cnblogs.com/wt645631686/p/13181413.html

上一篇：Spring02 ：Bean对象的创建和管理

下一篇：python+selenium2自动化---设置元素等待

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：php实现最大自序和算法
文章链接：http://soscw.com/index.php/essay/83862.html

亲，登录后才可以留言！

php实现最大自序和算法

评论

热门文章

推荐文章

最新文章

置顶文章