Python 中的 Kadanes 演算法

下面，我們將討論 Kadanes 演算法及其求解「最大子陣和」問題的性質。我們將理解演算法的概念，並處理相同的 Python 代碼以及示例及其相應的輸出。最後，我們將討論演算法的時間複雜度和 Kadanes 演算法的實際應用。

因此，讓我們開始吧。

理解 Kadanes 演算法

Kadanes 演算法是在動態規劃的幫助下解決問題的流行方法之一。眾所周知，最大子陣問題是動態規劃領域的熱門問題之一。我們一定認為問題看起來很簡單，問題的輸出將是數組中所有數據元素的總和。然而，這似乎不對。我們還會遇到負整數作為數組中的數據元素，它可以減少整個數組的總和。因此，我們將藉助 Kadanes 演算法來解決這個問題。

Kadanes 演算法用於尋找一維整數陣列中具有最大可能和的連續子陣列。在理解了問題的陳述之後，每個人的主要方法將是應用暴力方法並解決問題。然而，通過這樣做，解決方案的時間複雜度將是 O(n^2)，這一點也不令人印象深刻。因此，我們將使用 Kadanes 演算法來解決這個問題，在兩個變數的幫助下遍歷整個數組，以跟蹤迄今為止的總和和最大總和。使用該演算法時要注意的最重要的方面是我們將更新兩個變數的條件。

對最大子陣和演算法的理解

現在讓我們考慮最大子陣列和演算法的基本步驟，如下所示:

第一步:我們必須初始化 max_till_now = 0

第二步:我們必須初始化max _ end = 0

第 3 步:我們必須為數組中的每個數據元素重複第 4 步到第 6 步。

第四步:我們必須設置最大結束=最大結束+ a[i]

第五步:如果 (max_ending < 0) 那麼我們必須設置 max_ending = 0

第六步:如果(max till now<max _ end)那麼我們必須設置max till now = max _ end

第七步:我們必須返回max toll now

在演算法的上述步驟中，我們使用了 max_ending 來查找數組的所有正數據元素，使用了 max_till_now 來查找所有正段中數據元素的最大和。因此，每次我們在與 max_till_now 比較時得到正和，我們就能夠用更大的和來更新它。

因此，每當 max_ending 變為負時，我們將它設置為零，並且對於每次迭代，我們將檢查 max_till_now 小於 max_ending 的條件，以便在條件返回 True 時更新 max_till_now 。

用圖形表示理解 Kadanes 演算法

讓我們考慮以下關於整數數組的例子。

圖 1: 整數數組

圖 2: 我們將初始化 max_till_now = 0 和max _ end = 0(n = 0)。

圖 3: 然後我們會得到max toll now = 0和max _ end = 0為n = 1；但是對於 n = 2 ，我們會得到 max_till_now = 4 和max _ end = 4。

圖 4: 然後我們賦值 n = 3 和 4 ，分別得到 max_till_now = 4 和max _ end = 3，以及 max_till_now = 4 和max _ end = 1。

圖 5: 我們將得到max toll now = 6(6>4)為n = 5**max _ end = 6**。

圖 6: 對於 n = 6 ，我們還會得到max toll now = 6和max _ end = 4。

因此，從上面的例子中，我們將找到從 n = 2 到 n = 5 的最大子陣列，最大和將是 6 。

用 Python 代碼理解 Kadanes 演算法

讓我們考慮下面演示 Kadanes 演算法工作的代碼片段。

示例:

# defining the function to find the maximum subarray sum
def max_Subarray_Sum(my_array, array_size):
    # assigning the variables
    maxTillNow = my_array[0]
    maxEnding = 0

    # using the for-loop
    for n in range(0, array_size):
        maxEnding = maxEnding + my_array[n]
        # using the if-elif-else statement
        if maxEnding < 0:
            maxEnding = 0

        elif (maxTillNow < maxEnding):
            maxTillNow = maxEnding

    return maxTillNow
# defining the array
my_array = [-2, -3, 4, -1, -2, 5, -3]
# printing the maximum subarray sum for the users
print("Maximum Subarray Sum:", max_Subarray_Sum(my_array, len(my_array)))

輸出:

Maximum Subarray Sum: 6

說明:

在上面的代碼片段中，我們定義了一個函數為 max_Subarray_Sum ，取兩個參數分別為 my_array 和 array_sum 。然後，我們將變數最大值賦給數組的第一個索引值，並將最大值賦為零。然後我們使用 for-loop 遍歷整個數組。我們還使用了 if-elif-else 條件語句並返回 maxTillNow 。最後，我們為用戶定義了數組並列印了最大子數組和，在上例中為 6 。

理解時間複雜性

Kadanes 對由整數n個數據元素組成的數組的演算法的時間複雜度被定義為 O(n) ，因為在程序中只執行一個 for循環。同樣，演算法的輔助空間複雜度為 O(1) 。

了解應用

Kadanes 演算法有各種各樣的應用，其中一些如下所述:

1. Kadane 的演算法是為提供的整數數組找到最大子數組和。
2. 它被用作圖像處理的演算法。
3. 它還可以用來解決「有序車站旅行」和「沿海旅館」等問題。
4. 它也用於商業分析。

結論

最後，我們可以得出結論，在解決尋找最大子陣和的問題陳述時，解決方案似乎並不容易和簡單。然而，Kadanes 的演算法簡化了這類問題的求解，實現了時間複雜度最小的求解。這是可能的，因為 Kadanes 的演算法利用該技術來收集達成解決方案所需的信息，避免不必要的數據存儲。因此，我們可以把這種演算法看作是動態規劃方法的一個簡單例子，在現實世界中有許多實際應用。