PHP中如何实现连续子数组最大和问题的两种算法？

本文共计593个文字，预计阅读时间需要3分钟。

本文以实例讲述了PHP实现求连续子数组最大和的问题，并介绍了两种解决方案。

问题描述：求连续子数组中的最大和。

问题描述：输入一个整数数组，数组中包含正数和负数，要求找出连续子数组中的最大和。

解决方案一：动态规划phpfunction maxSubArraySum($arr) { $maxSum=$arr[0]; $currentSum=$arr[0];

for ($i=1; $i

return $maxSum;}

解决方案二：分治法phpfunction maxCrossingSum($arr, $left, $right) { if ($left==$right) { return $arr[$left]; }

$mid=($left + $right) / 2;

$leftSum=$maxCrossingSum($arr, $left, $mid); $rightSum=$maxCrossingSum($arr, $mid + 1, $right); $crossSum=$this->maxCrossingSumUtil($arr, $left, $mid, $right);

return max($leftSum, $rightSum, $crossSum);}

function maxCrossingSumUtil($arr, $left, $mid, $right) { $sum=0; $leftMax=PHP_INT_MIN; $rightMax=PHP_INT_MIN;

for ($i=$mid; $i >=$left; $i--) { $sum +=$arr[$i]; if ($sum > $leftMax) { $leftMax=$sum; } }

$sum=0; for ($i=$mid + 1; $i $rightMax) { $rightMax=$sum; } }

return $leftMax + $rightMax;}

分享给广大读者，供大家参考。

本文实例讲述了PHP实现求连续子数组最大和问题2种解决方法。分享给大家供大家参考，具体如下：

问题描述

求子数组的最大和

题目描述：

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

关于连续子数组最大和这个问题，有两种解法，一种是动态规划

解法如下：

function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0]; for($i = 1; $i < count($arr); $i++){ if($curSum > 0) $curSum += $arr[$i]; else $curSum = $arr[$i]; if($curSum > $maxSum) $maxSum = $curSum; } return $maxSum; }

还有一种是扫描法

function getMaxSubSum($arr){ $curSum = 0; $maxSum = 0; for($i = 0; $i < count($arr); $i++ ){ $curSum += $arr[$i]; if($curSum <= 0) $curSum = 0; if($curSum > $maxSum) $maxSum = $curSum; } if($maxSum == 0){ $maxSum = $arr[0]; for($i = 1; $i < count($arr); $i++){ if($maxSum < $arr[$i] ) $maxSum = $arr[$i]; } } return $maxSum; }

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《php字符串(string)用法总结》、《php常用函数与技巧总结》、《PHP错误与异常处理方法总结》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。