最大連續子數組總和的 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."<br>";
	echo "Starting index ". $start . "<br>".
			"Ending index " . $end . "<br>";
}
// 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 中尋找最大和連續子數組的有效解決方案。

以上是最大連續子數組總和的 PHP 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！