求连续子数组最大和的 PHP 程序
什么是 PHP?
PHP(超文本预处理器)是一种广泛用于 Web 开发的服务器端脚本语言。它允许开发人员将代码嵌入 HTML 文件中，从而创建动态网页并与数据库进行交互。PHP 以其简洁、多功能以及与主流数据库的广泛集成能力而闻名。它提供了广泛的扩展，并拥有庞大的开发者社区，确保了充足的资源和支持。
求连续子数组最大和的 PHP 程序
4 + (-1) + 2 + 1 = 6
最大连续和 = 6
使用 Kadane 算法
Kadane 算法是一种高效的算法，用于在给定数组中查找连续子数组的最大和。它由 Jay Kadane 于 1984 年开发。
该算法通过迭代扫描数组并维护两个变量来工作:max_so_far 和 max_ending_here。算法的工作原理如下:
将 max_so_far 和 max_ending_here 变量初始化为数组的第一个元素，如果数组包含负数，则初始化为最小值(例如 PHP_INT_MIN)。
从第二个元素开始遍历数组。
对于每个元素，通过将当前元素添加到 max_ending_here 中来更新 max_ending_here。
如果 max_ending_here 为负数，则将其重置为 0，因为将当前元素包含在子数组中会减少总和。
如果 max_ending_here 大于 max_so_far，则使用新的最大和更新 max_so_far。
对数组的其余元素重复步骤 3 至 5。
之后遍历整个数组，max_so_far 将保存连续子数组的最大和。
返回 max_so_far 作为结果。
Kadane 算法的时间复杂度为 O(n)，其中 n 是数组的大小，因为它只需要遍历数组一次。这使得它成为查找连续子数组最大和的有效解决方案。
示例
<?php
// 打印最大连续数组和的 PHP 程序
function maxSubArraySum($a, $size)
{
$max_so_far = PHP_INT_MIN;
$max_ending_here = 0;
for ($i = 0; $i < $size; $i++)
{
$max_ending_here = $max_ending_here + $a[$i];
if ($max_so_far < $max_ending_here)
$max_so_far = $max_ending_here;
if ($max_ending_here < 0)
$max_ending_here = 0;
}
return $max_so_far;
}
// 驱动代码
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = count($a);
$max_sum = maxSubArraySum($a, $n);
echo "Maximum contiguous sum is " ,
$max_sum;
?>
输出
Maximum contiguous sum is 6
使用算法范式:动态规划
示例
<?php
function maxSubArraySum($a, $size)
{
$max_so_far = $a[0];
$curr_max = $a[0];
for ($i = 1; $i < $size; $i++)
{
$curr_max = max($a[$i],
$curr_max + $a[$i]);
$max_so_far = max($max_so_far,
$curr_max);
}
return $max_so_far;
}
// 驱动代码
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
echo "Maximum contiguous sum is " .
$max_sum;
?>
输出
Maximum contiguous sum is 6
使用起始和结束索引的另一种方法
示例
<?php
// 打印最大连续数组和的 PHP 程序
function maxSubArraySum($a, $size)
{
$max_so_far = PHP_INT_MIN;
$max_ending_here = 0;
$start = 0;
$end = 0;
$s = 0;
for ($i = 0; $i < $size; $i++)
{
$max_ending_here += $a[$i];
if ($max_so_far < $max_ending_here)
{
$max_so_far = $max_ending_here;
$start = $s;
$end = $i;
}
if ($max_ending_here < 0)
{
$max_ending_here = 0;
$s = $i + 1;
}
}
echo "Maximum contiguous sum is ".
$max_so_far."
";
echo "Starting index ". $start . "
".
"Ending index " . $end . "
";
}
// 驱动代码
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
?>
输出
Maximum contiguous sum is 6 Starting index 3 Ending index 6
结论
用于查找最大和连续子数组的 PHP 程序利用了动态规划和 Kadane 算法。动态规划方法通过将问题分解为更小的子问题并将解决方案存储在数组中来有效地解决问题。
Kadane 算法是该程序的关键组件，负责查找最大和连续子数组。它迭代数组，通过添加当前元素或开始新的子数组来不断更新当前和。遇到的最大和存储在 $maxSum 变量中。该程序可以有效地处理数组中的正数和负数。它通过跟踪起始和结束索引来识别和最大的子数组，从而允许使用 array_slice 提取子数组。
通过利用动态规划和 Kadane 算法，该程序实现了 O(n) 的时间复杂度，其中 n 是数组的大小。这确保了在 PHP 中寻找最大和连续子数组的有效解决方案。
