© Jirsak/Shutterstock.com
當您處理數據集時，它們可能採用數組形式。而且這些數組往往是連續的。這意味著數據值之間沒有“中斷”——它們存儲在單個內存塊中。當涉及到經典的最大子數組問題時，這種類型的數組佔據了中心位置。雖然有幾種方法可以解決這個問題，但最好的方法之一是使用 Kadane 的算法。如果您想知道如何使用此算法，以及它如何適用於動態規劃領域，那麼您來對地方了。和我們一起探索 Kadane 的算法以及它如何用於解決最大子數組問題。
什麼是最大子數組問題?
最大子數組問題也稱為最大值連續子數組問題。簡單來說，這個問題的任務是在大小為 N 的數組 arr[] 中找到最大的連續子數組。也就是說，找到數組中整數相加的最大可能總和，整數之間沒有間斷。例如，如果我們採用數組 [4,-1, 2, 1]，最大總和就是所有整數的總和，即 6。
對於小數據集，這可能是一個相對簡單的任務，並且可以使用所謂的“蠻力方法”相當容易地解決。這基本上意味著以犧牲整體效率為代價使用最簡單的計算。這樣，我們可以從第 0 個索引開始，計算每個可能的子數組的和，從元素 A[0] 開始。我們可以計算這些子數組的總和，從 A[1] 開始一直到 A[n-1]，其中 n 是數組大小。如果我們將子數組的最大和稱為索引 i 處的 local_maximum，我們可以計算所有這些，然後通過找到 local_maximums 的最大值來完成。這將為我們提供最大可能的總和，可以描述為 global_maximum。
如您所料，這對於非常小的數組可能工作得很好，但對於較大的數據集來說效率很低。時間複雜度是二次方的，即 O(n2)，這意味著複雜度隨著輸入大小的增加而迅速增加。因此，我們將需要一個更高效、更優雅的流程。這就是動態規劃的用武之地。
動態規劃如何提供幫助?
動態規劃是一種通過將復雜問題簡化為一系列更簡單問題來解決複雜問題的方法。這些比較容易的問題被解決了，他們的解決方案被存儲在一個數據結構中，比如數組。當我們解決相同類型的問題時，可以訪問這些解決方案，避免再次解決它們並加快整體計算速度。
如果我們能夠應用這些原則，那將是非常有益的動態規劃到我們的最大子數組問題。幸運的是，我們可以做到，而這正是 Kadane 的算法打算要做的。那麼，讓我們開始吧。
動態規劃是一種通過將復雜問題簡化為更簡單問題的集合來解決複雜問題的方法。
©hafakot/Shutterstock.com
Kadane 的算法
如前所述，Kadane 的算法使用動態規劃來計算最大子數組問題的有效解決方案。該算法通過在當前索引處存儲最大和連續子數組來工作。然後將其與迄今為止找到的最大總和進行比較。如果它大於目前找到的最大總和，則用新值更新。
Kadane 算法的一個主要優勢是它的速度，其時間複雜度為 O(n)。這意味著時間複雜度隨著輸入大小的增加而線性增加，這比蠻力方法的二次時間複雜度要好得多。空間複雜度也很好，因為算法是穩定的——這意味著在該過程中需要恆定數量的內存，因為只需要存儲兩個變量（它們是 global_maximum 和 local_maximum）。
Kadane 算法實戰
讓我們再次使用數組 [4,-1, 2, 1]。如果我們反轉蠻力方法，從元素 A[n]（在本例中為 1）開始，我們可以計算每個可能的子數組的總和，然後繼續 A[n-1]、A[n-2]
查看最後兩個元素 A[3] 和 A[4]，我們可以看到 local_maximum 分別為 5 和 6。但是，如果我們知道 local_maximum[3]，我們就不需要計算 A[4] 的所有子數組和。這是因為我們已經知道 A[3] 和 local_maximum[3] 的結果。我們只需要檢查兩個子數組，一個只包含 A[4] 以及 A[4] 和 local_maximum[3] 的總和。在這種情況下，這將是 A[4} + local_maximum[3]，即 6。如果我們計算 A[4] 的所有子數組和，這與我們得到的答案相同。
這個原則是 Kadane 算法的基礎，可以描述如下:
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
或者，換句話說，索引i處的local_maximum是A[i]的最大值以及A[i]和索引i-1處的local_maximum之和。
因此，我們只需要找到A[i]的最大值和 A[i] + local_maximum[i-1] 找到每個索引 i 處的最大值。因此，我們只需要找到每個local_maximum，就可以找到最大的子數組。這是解決最大子數組問題的更有效方法。
Kadane 算法的工作原理
讓我們來看看 Kadane 算法用於計算最大子數組的步驟。
p> 該算法將只需要一個循環，從 i[0[ 到 i[n-1] 迭代。將為每個元素計算 local_maximum[i]，這取決於 local_maximum[i-1]。與 local_maxium 進行比較到 global_maximum。如果它更大，則將更新 global_maximum。對每個索引重複此操作，直到找到連續子數組的最大總和。
Kadane 算法的實現
為了展示 Kadane 算法的實現方式，我們將在 Spyder 環境中使用 Python。讓我們來看看代碼在實踐中是如何工作的。
from sys import maxsize def solveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=max(input[i], input[i] + localMaxSum) if(localMaxSum>globalMaxSum): globalMaxSum=localMaxSum 返回 globalMaxSum if_name_==”_main_”input=[1,-2, 5,-3, 4,-1, 6] result=solveMaxSubArrayProblem(input) print(result) 11
首先，Python 中正確的縮進是正確執行代碼的關鍵。首先，我們導入用於查找最大值的“maxsize”函數。
接下來，我們將“solveMaxSubArrayProblem”定義為長度為 n 的“輸入”數組的函數, globalMaxSum 初始化為最小整數值。這樣做是為了確保計算出的任何子數組總和都將大於該值。
local_maximum 會發生變化並初始設置為 0。
“for”指的是循環，用於遍歷每個數組元素。
對於每次迭代，“localMaxSum”更新為當前元素的 localMaxSum 或元素加上前一個 localMaxSum。
如果localMaxSum 大於當前的 globalMaxSum，更新後者以反映此更改。
一旦迭代過程完成，globalMaxSum 等於最大連續子數組，並返回此結果。
最後，“if __name__==“”__main__””通過創建後面的數組並在其上使用定義的函數來測試函數，然後打印結果。
對於數組 [1 ,-2, 5,-3, 4,-1, 6]，最大連續子數組的和為11。
©”TNGD”.com
總結
我們介紹了動態規劃背後的原理。我們還展示了 Kadane 的算法如何使用它來解決最大子數組問題。描述了這樣做的優點。 Kadane 的算法相對易於理解和使用，具有高效的時間和空間複雜度。在解決最大子數組問題時，Kadane 算法是最快的方法之一。
下一個…
Kadane 算法:一種解決最大子數組問題的有效方法, Explained with Photos FAQs (Frequently Asked Questions)
什麼是子數組?
子數組是不間斷的數組的一部分，即沒有中斷整數之間。這被描述為連續的。一個子數組可以由一個元素組成。它們主要用於處理數據集，例如查找最大連續子數組。
什麼是動態規劃?
動態規劃是指通過將復雜問題分解為更簡單的問題來解決複雜問題的技術。每個子解只需要計算一次，並存儲在臨時緩存中。因此，避免了冗餘計算，從而顯著加快了處理速度。動態規劃通常用於優化解決方案和設計算法，例如用於尋找圖中最短路徑的 Bellman-Ford 算法。通常，子問題是自下而上解決的，這意味著首先解決最簡單的問題。然後將這些解決方案組合起來解決初始問題。
什麼是最大子數組問題?
這是一個經典的編程問題，涉及尋找最大和整數數組中的連續子數組。這個問題的解決方案在金融、數據分析和信號處理等領域有很多應用。解決此問題的最有效算法是 Kadane 算法。
什麼是 Kadane 算法?
Kadane 算法是解決最大連續子數組問題的有效方法.該算法通過計算 local_maximum 和 global_maximum 來工作。通過從左邊開始遍歷數組，這些變量在每一步都會更新，如果 local_maximum 的值更大，那麼到目前為止的最大值將替換 global_maximum 。計算完所有局部最大值後，最大連續子數組就已知並等於全局最大值。
解決最大子數組問題的蠻力方法是什麼?
蠻力方法涉及遍歷數組中所有可能的子數組併計算子數組的總和。然後可以找到最大的連續子數組，但是這個過程不是很有效，因為必須計算每個單獨的子數組。
使用 Kadane 算法的缺點是什麼?
Kadane的算法雖然簡單高效，但真正只能用來解決最大子數組問題。它產生的輸出也是有限的，因為它只包含最大子數組的總和。沒有提供有關陣列本身的信息，這對於某些應用程序可能是必需的。最後，雖然算法很快，但解決方案並非在所有情況下都是最優的。
Kadane 算法的時間複雜度是多少?
時間複雜度為Kadane 的算法是 O(n)。
Kadane 的算法可以用於非連續數組嗎?
不能，該算法不能用於不連續的數組。
如何修改 Kadane 的算法以找到總和最小的子數組?
我們可以簡單地將 maxsize 函數替換為 minsize , 並將變量初始化為無窮大而不是零。
Kadane 的算法可以與所有負整數的數組一起使用嗎?
是的，該算法將在這種情況下返回具有最小負和的子數組。