最大子陣演算法基本資訊

最大子陣列問題是在具有最大總和的一維數字陣列內找到連續子陣列的方法。

該問題最初由布朗大學的 Ulf Grenander 於 1977 年提出，作為數字化影象中模式的最大似然估計的簡化模型。

我們可以像這樣的問題，讓我們考慮各種整數的列表。我們可能對哪個完全相鄰的子集具有最大總和感興趣。例如，如果我們有陣列 [0, 1, 2, -2, 3, 2]，則最大子陣列是 [3, 2]，其總和為 5。

蠻力的解決方案：

找出解決方案的效率最低。在這裡，我們將最終遍歷每個可能的子陣列，然後找到所有子陣列的總和。最後，比較所有值並找出最大子陣列。

蠻力方法的虛擬碼：

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Brute-Force 方法的時間複雜度是 O(n^2)。讓我們轉向分而治之的方法。

分而治之的解決方案：

找到左側子陣列的總和，右側的子陣列。然後，看看跨越中心分界的所有那些，最後返回最大總和。因為這是一個分而治之的演算法，我們需要有兩個不同的功能。

首先是分步，

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

在第二部分中，分離在第一部分中建立的不同部分。

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

Divide and Conquer 方法的時間複雜度是 O(nlogn)。讓我們轉向動態程式設計方法。

動態規劃方法：

該解決方案也稱為 Kadane 演算法。它是線性時間演算法。這個解決方案由 Joseph B. Kadane 在 70 年代末期給出。

該演算法只是迴圈，不斷改變當前的最大總和。有趣的是，這是動態程式設計演算法的一個非常簡單的例子，因為它需要重疊問題並減少它，以便我們找到更有效的解決方案。

Kadane 演算法的虛擬碼：

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

Kadane 演算法的時間複雜度是 O(n)。