C#でアルゴリズムとデータ構造1 ～最大部分配列問題～

今日は最大部分配列問題（maximum-subarray problem）について。

最大部分配列問題とは

入力

要素数が1以上の1次元配列。

出力

入力の1次元配列の全ての部分配列（配列の一部をそのまま切り出したもの。要素の順序を並べ替えたり、一部の要素を取り除いたりしてはならない）の中で、部分配列のそれぞれの要素の値の総和が最大となるようなもの。

算法1

考え方

入力の1次元配列の全ての部分配列のそれぞれの要素の値の総和を計算し、総和が最大となるような部分配列を探し出せば良い。
全ての1次元配列の部分配列は、元の1次元配列と、左端の要素の番号と、右端の要素の番号から成る3つ組で表せる。たとえば、要素数が10の1次元配列Aの3つ目の要素から5つ目の要素までから成る部分配列は、正に、元の1次元配列と、左端の要素の番号である3と、右端の要素の番号である5から成る3つ組で表せる（これを、たとえば、A[3...5]と表記することができるだろう）。
すなわち、1次元配列の特定の部分配列を求めるには、元の1次元配列は当然所与のものとして、左端の要素の番号と右端の要素の番号を求めれば良いということである。
この算法では、左端の要素の番号を0とした場合から始め、1ずつ増やしていく。左端の要素の番号毎に、右端の要素の番号を左端の要素の番号とした場合から始め、1ずつ増やしていく。これによって定まるそれぞれの部分配列に対して、部分配列のそれぞれの要素の値の総和を計算し、最大のものを求める。

計算時間

$ \Theta(n^3) $

##コード

public class Subarray
{
    public Subarray(int[] _array, int _left, int _right)
    {
        Array = _array;
        Left = _left;
        Right = _right;
    }

    public int[] Array { get; set; }
    public int Left { get; set; }
    public int Right { get; set; }
}

public static int MaxSubarray1(Subarray input)
{
    int left = input.Left;
    int right = input.Right;
    int maxSum = input.Array[input.Left];

    for (int i = input.Left; i <= input.Right; i++)
        for (int j = i; j <= input.Right; j++)
        {
            int sum = 0;
            for (int k = i; k <= j; k++)
                sum += input.Array[k];

            if (maxSum < sum)
            {
                left = i;
                right = j;
                maxSum = sum;
            }
        }

    input.Left = left;
    input.Right = right;

    return maxSum;
}

算法2

考え方

算法1では、部分配列のそれぞれの要素の値の総和を毎回計算しているが、右端の要素の番号は1ずつ増加するため、右端の要素を1個ずつ右にずらしていくのと同時に総和を計算することができる。

計算時間

$ \Theta(n^2) $

##コード

public static int MaxSubarray2(Subarray input)
{
    int left = input.Left;
    int right = input.Right;
    int maxSum = input.Array[input.Left];

    for (int i = input.Left; i <= input.Right; i++)
    {
        int sum = 0;

        for (int j = i; j <= input.Right; j++)
        {
            sum += input.Array[j];

            if (maxSum < sum)
            {
                left = i;
                right = j;
                maxSum = sum;
            }
        }
    }

    input.Left = left;
    input.Right = right;

    return maxSum;
}

算法3

考え方

分割統治法を用いることができる。入力の1次元配列を左半分と右半分に2分割して問題の大きさを半分にすることができる。ただし、部分配列が左半分と右半分に跨る場合も考慮しなければならない。

計算時間

$ \Theta(n \log n) $

##コード

public static int MaxSubarray3(Subarray input)
{
    if (input.Left == input.Right)
        return input.Array[input.Left];

    int mid = (input.Left + input.Right) / 2;

    Subarray leftSubarray = new Subarray(input.Array, input.Left, mid);
    Subarray rightSubarray = new Subarray(input.Array, mid + 1, input.Right);

    int leftSum = MaxSubarray3(leftSubarray);
    int rightSum = MaxSubarray3(rightSubarray);
    int crossSum = MaxCrossingSubarray(input, mid);

    if (leftSum >= rightSum && leftSum >= crossSum)
    {
        input.Left = leftSubarray.Left;
        input.Right = leftSubarray.Right;

        return leftSum;
    }
    else if (rightSum >= leftSum && rightSum >= crossSum)
    {
        input.Left = rightSubarray.Left;
        input.Right = rightSubarray.Right;

        return rightSum;
    }
    else
        return crossSum;
}

public static int MaxCrossingSubarray(Subarray input, int mid)
{
    int s = input.Array[mid];
    int left = mid;
    int leftSum = input.Array[mid];
    for (int i = mid - 1; i >= input.Left; i--)
    {
        s += input.Array[i];
        if (leftSum < s)
        {
            left = i;
            leftSum = s;
        }
    }

    s = input.Array[mid + 1];
    int right = mid + 1;
    int rightSum = input.Array[mid + 1];
    for (int i = mid + 1 + 1; i <= input.Right; i++)
    {
        s += input.Array[i];
        if (rightSum < s)
        {
            right = i;
            rightSum = s;
        }
    }

    input.Left = left;
    input.Right = right;

    return leftSum + rightSum;
}

算法4

考え方

Kadaneの算法（Kadane's algorithm）と言う。
最初に、左端の要素が入力の1次元配列の左端の要素であり、右端の要素も同様に入力の1次元配列の左端の要素であるような場合を考え、右端の要素を1個ずつ右にずらしていき、そのような部分配列でそれぞれの要素の値の総和が最大となるような左端の要素を求め、それまでのそれぞれの要素の値の総和が最大となる部分配列と比較する。

計算時間

$ \Theta(n) $

##コード

public static int MaxSubarray4(Subarray input)
{
    int leftEndingHere = input.Left;
    int maxEndingHere = input.Array[input.Left];

    int left = input.Left;
    int right = input.Right;
    int max = input.Array[input.Left];

    for (int i = input.Left + 1; i <= input.Right; i++)
    {
        int sum = maxEndingHere + input.Array[i];

        if (sum < input.Array[i])
        {
            leftEndingHere = i;
            maxEndingHere = input.Array[i];
        }
        else
            maxEndingHere = sum;

        if (max < maxEndingHere)
        {
            left = leftEndingHere;
            right = i;
            max = maxEndingHere;
        }
    }

    input.Left = left;
    input.Right = right;

    return max;
}