用於計算最大連續子陣列和的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變為負數，則將其重置為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 code
$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;
}
// 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 Code
$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中查詢最大連續子陣列和的高效解決方案。