Go 語言實現 Kadane 演算法

---

有一個著名的最大子陣列和問題，其中我們有一個一維陣列，必須找到該子陣列中的最大和。為了解決這個問題，最簡單的辦法是找到所有子陣列，將它們的元素求和，並返回最大值，但時間複雜度將為 O(N*N)。為了減少這一點，有一種演算法可以將時間複雜度從 O(N*N) 降低到 O(N)，稱為 Kadane 演算法。

在程式設計中，有一些基於動態規劃概念的演算法，其中問題被分解成子問題，並儲存結果，用於類似的子問題。Kadane 演算法也是動態規劃演算法之一，它將使用前一個索引儲存到當前索引為止的最大子陣列和。

演算法

步驟 1：使用 import 關鍵字在頂部匯入所需的包。

步驟 2：然後 main 函式將首先執行。

• 首先，我們宣告並初始化陣列。

• 現在我們正在呼叫 maxSumSubArray() 函式，在其中我們實現了 Kadane 演算法。

步驟 3：maxSumSubArray() 函式實現

• 初始化名為 sum 和 maxSum 的變數，並分別初始化為 0 和 INT_MIN。

• 對陣列的每個元素執行 for 迴圈。在每次迭代中

• 將當前索引值新增到變數 sum 中。

• 如果條件是檢查 sum 是否大於 maxSum，如果是，則我們將 dp maxSum = sum。

• 另一個 if 條件是檢查 sum 是否小於零，如果是，則使 sum = 0。

• 返回 maxSum 值。

步驟 4：列印給定陣列中由 maxSumSubArray() 函式返回的最大子陣列和。

示例

讓我們找到陣列 {3, −3, 4, 2, −1, 5} 的最大子陣列和。

Sum = 0

maxSum = INT_MIN

迭代 1

At i = 0 array[i] = 3
Sum = 0 + 3
    = 3
maxSum < sum
maxSum = 3  

迭代 2

At i = 1 array[i] = −3
Sum = 3 + (−3)
    = 0
maxSum > sum
maxSum = 3

迭代 3

At i = 2 array[i] = 4
Sum = 0 + 4
    = 4
maxSum < sum
maxSum = 4

迭代 4

At i = 3 array[i] = 2
Sum = 4 + 2
    = 6
maxSum < sum
maxSum = 6

迭代 5

At i = 4 array[i] = −1
Sum = 6 + (−1)
    = 5
maxSum > sum
maxSum = 6

迭代 6

At i = 5 array[i] = 5
Sum = 5 + (5)
   = 10
maxSum < sum
maxSum = 10

示例

在以下示例中，我們將演示如何開發一個 Go 語言程式來實現 Kadane 演算法。

package main

import (
    "fmt"
    "math"
)

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func maxSumSubArray(array []int, size int) int {
    // declaring variable sum of int type
    // and an iterator i
    var sum, maxSum, i int

    // initializing the variables declared above
    sum = 0
    maxSum = math.MinInt
    i = 0

    // running for loop from o to the size of the array
    for i < size {
        sum = sum + array[i]
        if sum > maxSum {
            maxSum = sum
        }
        if sum < 0 {
            sum = 0
        }
        i++
    }
    return maxSum
}

func main() {
    // declaring and initializing the
    // array of size 6 using the shorthand method
    array := []int{-2, -3, 4, -1, -2, 1, 5, -3}

    fmt.Println("Golang program to find the maximum sum subarray in the given array using Kaden's algorithm.")
    fmt.Print("array: ")
    printArray(array, len(array))

    // calling maxSumSubArray() function by passing array and length as a parameter
    sum := maxSumSubArray(array, len(array))

    fmt.Println("The maximum sum is", sum)
}

輸出

Golang program to find the maximum sum subarray in the given array using Kaden's algorithm.
array: -2 -3 4 -1 -2 1 5 -3
The maximum sum is 7

結論

這是 Kadane 演算法的實現，它是一種動態規劃演算法，用於查詢最大子陣列和。為了在最短的時間內解決面試中的此類問題，每個人都使用 Kadane 演算法。要了解有關 Go 語言的更多資訊，您可以瀏覽這些 教程。