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);
}
}