How to implement Kadane algorithm for 2D matrix [c

问题:

I am trying to figure out how to implement C# code for Kadane's 2D Matrix algorithm. I found a 1D version here:

Kadane's algorithm to find subarray with the maximum sum

But I want a 2D version. Basically, given a Matrix N x N of positive and negative numbers, I need to find a submatrix where sum of all elements would be the greatest.

回答1:

Figured it out. For those who is interested

    static void Main(string[] args)
    {
        int[,] array2D = new int[,]
            {
                { 1, 2 }, 
                { -3, 4 }, 
                { 5, -6 }, 
                { -7, -8 }
            };
        var max = GetMaxMatrix(array2D);
        Console.WriteLine(max);
    }

    public static int GetMaxMatrix(int[,] original)
    {
        int maxArea = int.MinValue; 
        int rowCount = original.GetLength(0);
        int columnCount = original.GetLength(1);
        int[,] matrix = PrecomputeMatrix(original);
        for (int row1 = 0; row1 < rowCount; row1++)
        {
            for (int row2 = row1; row2 < rowCount; row2++)
            {
                for (int col1 = 0; col1 < columnCount; col1++)
                {
                    for (int col2 = col1; col2 < columnCount; col2++)
                    {
                        maxArea = Math.Max(maxArea, ComputeSum(matrix, row1, row2, col1, col2));
                    }
                }
            }
        }
        return maxArea;
    }

    private static int[,] PrecomputeMatrix(int[,] matrix)
    {
        var sumMatrix = new int[matrix.GetLength(0), matrix.GetLength(1)];
        for (int i = 0; i < matrix.GetLength(0); i++)
        {
            for (int j = 0; j < matrix.GetLength(1); j++)
            {
                if (i == 0 && j == 0)
                { // first cell
                    sumMatrix[i, j] = matrix[i, j];
                }
                else if (j == 0)
                { // cell in first column
                    sumMatrix[i, j] = sumMatrix[i - 1, j] + matrix[i, j];
                }
                else if (i == 0)
                { // cell in first row
                    sumMatrix[i, j] = sumMatrix[i, j - 1] + matrix[i, j];
                }
                else
                {
                    sumMatrix[i, j] = sumMatrix[i - 1, j] +
                    sumMatrix[i, j - 1] - sumMatrix[i - 1, j - 1] + matrix[i, j];
                }
            }
        }
        return sumMatrix;
    }

    private static int ComputeSum(int[,] sumMatrix, int i1, int i2, int j1, int j2)
    {
        if (i1 == 0 && j1 == 0)
        { // starts at row 0, column 0
            return sumMatrix[i2, j2];
        }
        else if (i1 == 0)
        { // start at row 0
            return sumMatrix[i2, j2] - sumMatrix[i2, j1 - 1];
        }
        else if (j1 == 0)
        { // start at column 0
            return sumMatrix[i2, j2] - sumMatrix[i1 - 1, j2];
        }
        else
        {
            return sumMatrix[i2, j2] - sumMatrix[i2, j1 - 1]
            - sumMatrix[i1 - 1, j2] + sumMatrix[i1 - 1, j1 - 1];
        }
    }

回答2:

This was too tempting of a problem to leave untouched :-)

I found a C/C++ solution to the problem here, and basically I have translated it into C#. The solution is for int:s, but it should be fairly easy to convert it into the numeric type of your liking. You might also want to return the results of findMaxSum in some way, I leave that as an exercise.

// Driver program to test 2D Kadane method
void Main()
{
    int[,] M = {{ 1,  2, -1, -4, -20},
                {-8, -3,  4,  2,   1},
                { 3,  8, 10,  1,   3},
                {-4, -1,  1,  7,  -6}};

    findMaxSum(M);
}

// Implementation of Kadane's algorithm for 1D array. The function returns the
// maximum sum and stores starting and ending indexes of the maximum sum subarray
// at addresses pointed by start and finish pointers respectively.
int kadane(int[] arr, out int start, out int finish, int n)
{
    // initialize sum, maxSum
    int sum = 0;
    int maxSum = Int32.MinValue;

    // Just some initial value to check for all negative values case
    start = -1;
    finish = -1;

    int local_start = 0; 
    for (int i = 0; i < n; ++i)
    {
        sum += arr[i];
        if (sum < 0)
        {
            sum = 0;
            local_start = i+1;
        }
        else if (sum > maxSum)
        {
            maxSum = sum;
            start = local_start;
            finish = i;
        }
    }

    // There is at-least one non-negative number
    if (finish != -1)
        return maxSum;

    // Special Case: When all numbers in arr[] are negative
    maxSum = arr[0];
    start = finish = 0;

    // Find the maximum element in array
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > maxSum)
        {
            maxSum = arr[i];
            start = finish = i;
        }
    }
    return maxSum;
}

// The main function that finds maximum sum rectangle in M[][]
void findMaxSum(int[,] M)
{
    int ROW = M.GetLength(0);
    int COL = M.GetLength(1);

    // Variables to store the final output
    int maxSum = Int32.MinValue;
    int finalLeft = -1, finalRight = -1, finalTop = -1, finalBottom = -1;

    // Set the left column
    for (int left = 0; left < COL; ++left)
    {
        // Initialize all elements of temp as 0
        int start, finish;
        int[] temp = new int[ROW];

        // Set the right column for the left column set by outer loop
        for (int right = left; right < COL; ++right)
        {
            // Calculate sum between current left and right for every row 'i'
            for (int i = 0; i < ROW; ++i)
                temp[i] += M[i, right];

            // Find the maximum sum subarray in temp[]. The kadane() function
            // also sets values of start and finish.  So 'sum' is sum of
            // rectangle between (start, left) and (finish, right) which is the
            //  maximum sum with boundary columns strictly as left and right.
            int sum = kadane(temp, out start, out finish, ROW);

            // Compare sum with maximum sum so far. If sum is more, then update
            // maxSum and other output values
            if (sum > maxSum)
            {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }

    // Print final values
    Console.WriteLine("(Top, Left) ({0},{1})", finalTop, finalLeft);
    Console.WriteLine("(Bottom, Right) ({0},{1})", finalBottom, finalRight);
    Console.WriteLine("Max sum is: {0}\n", maxSum);
}