最大子阵算法基本信息

最大子阵列问题是在具有最大总和的一维数字数组内找到连续子阵列的方法。

该问题最初由布朗大学的 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)。