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 的算法利用該技術來收集達成解決方案所需的信息，避免不必要的數據存儲。因此，我們可以把這種算法看作是動態規劃方法的一個簡單例子，在現實世界中有許多實際應用。