algorithm
最大サブアレイアルゴリズム

最大サブアレイアルゴリズム基本情報

最大サブアレイの問題は、最も大きな合計を持つ1次元の数値配列内の連続したサブアレイを見つける方法です。

問題はもともと、1977年にBrown UniversityのUlf Grenanderによって、デジタル化された画像のパターンの最尤推定のための単純化されたモデルとして提案された。

このような問題はありますが、さまざまな整数のリストを考えてみましょう。完全に隣接する部分集合が最大の和を持つことに興味があるかもしれません。たとえば、配列[0, 1, 2, -2, 3, 2] -2,3,2 [0, 1, 2, -2, 3, 2]場合、最大部分配列は[3, 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

ブルートフォース法の時間複雑度は O(n^2)です。だから、分裂と征服のアプローチに移動しましょう。

ソリューションを分割して克服するアプローチ：

左側のサブアレイの合計、右側のサブアレイを求めます。次に、中央の分割を横切るすべてのものを見て、最終的に最大合計を返します。これは分割征服アルゴリズムなので、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))

2番目の部分では、最初の部分で作成された別の部分を区切ります。

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のアルゴリズムとも呼ばれます。線形時間アルゴリズムです。この解決法は、70年代後半にJoseph B. Kadaneによって与えられています。

このアルゴリズムはループを通過し、現在の最大合計を連続的に変更します。興味深いことに、これは動的プログラミングアルゴリズムの非常に単純な例です。重複する問題を取り除き、より効率的なソリューションを見つけることができるためです。

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)です。

C＃の実装

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}