如何实现Kadane算法的二维矩阵 [英] How to implement Kadane algorithm for 2D matrix

问题描述

我试图找出如何实现C＃$ C $下Kadane的二维矩阵算法。我发现了一个1D版本在这里：

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

<一个href="http://stackoverflow.com/questions/9890227/kadanes-algorithm-to-find-subarray-with-the-maximum-sum">Kadane's算法来寻找子阵列的最大金额

不过，我希望有一个2D版本。基本上，考虑到正数和负数矩阵的N×N，我需要找一个子矩阵，其中所有元素的总和将是最大的。

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.

推荐答案

想通了。对于那些谁是有兴趣

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

这篇关于如何实现Kadane算法的二维矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！