极客笔记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 program to print largest
// contiguous array sum
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;
}
// Driver codea = 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);
}
returnmax_so_far;
}
// Driver Code
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 program to print largest
// contiguous array sum
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 . "
";
}
// Driver Codea = 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中寻找具有最大和的连续子数组的高效解决方案。