如何实现二维矩阵的Kadane算法

我试图弄清楚如何为Kadane的2D Matrix算法实现C＃代码。 我在这里找到了一个版本：

Kadane的算法用于查找具有最大总和的子arrays

但我想要一个2D版本。 基本上，给定正数和负数的矩阵N×N，我需要找到一个子矩阵，其中所有元素的总和将是最大的。

Answer 1

弄清楚了。 对于那些有兴趣的人

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

Answer 2

这是一个太诱人的问题，保持原状:-)

我在这里找到了解决这个问题的C / C ++解决方案，基本上我把它翻译成了C＃。 解决方案适用于int ：s，但将其转换为您喜欢的数字类型应该相当容易。 您可能还想以某种方式返回findMaxSum的结果，我将其findMaxSum练习。

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