Obtener la submatriz con sum máxima?

Entrada : una matriz bidimensional NxN – Matriz – con elementos positivos y negativos.

Salida : Una submatriz de cualquier tamaño, de modo que su sum es la máxima entre todas las submatrices posibles.

Requisito : la complejidad del algoritmo es de O (N ^ 3)

Historia: Con la ayuda del algoritmo, Larry y una modificación del algoritmo de Kadane, logré resolver parcialmente el problema, que es la única que determina la sum, a continuación, en Java.
Gracias a Ernesto que logró resolver el rest del problema que está determinando los límites de la matriz, es decir, las esquinas superior izquierda, inferior derecha, a continuación en Ruby.

Acerca de la recuperación de la submatriz real, y no solo la sum máxima, esto es lo que obtuve. Lo siento, no tengo tiempo para traducir mi código a su versión java, así que estoy publicando mi código Ruby con algunos comentarios en las partes clave

 def max_contiguous_submatrix_n3(m) rows = m.count cols = rows ? m.first.count : 0 vps = Array.new(rows) for i in 0..rows vps[i] = Array.new(cols, 0) end for j in 0...cols vps[0][j] = m[0][j] for i in 1...rows vps[i][j] = vps[i-1][j] + m[i][j] end end max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right] # these arrays are used over Kadane sum = Array.new(cols) # obvious sum array used in Kadane pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j for i in 0...rows for k in i...rows # Kadane over all columns with the i..k rows sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane pos.fill(0) local_max = 0 # we keep track of the position of the max value over each Kadane's execution # notice that we do not keep track of the max value, but only its position sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0]) for j in 1...cols value = vps[k][j] - (i==0 ? 0 : vps[i-1][j]) if sum[j-1] > 0 sum[j] = sum[j-1] + value pos[j] = pos[j-1] else sum[j] = value pos[j] = j end if sum[j] > sum[local_max] local_max = j end end # Kadane ends here # Here's the key thing # If the max value obtained over the past Kadane's execution is larger than # the current maximum, then update the max array with sum and bounds if sum[local_max] > max[0] # sum[local_max] is the new max value # the corresponding submatrix goes from rows i..k. # and from columns pos[local_max]..local_max # the array below contains [max_sum,top,left,bottom,right] max = [sum[local_max], i, pos[local_max], k, local_max] end end end return max # return the array with [max_sum,top,left,bottom,right] end 

Algunas notas para aclarar:

Uso una matriz para almacenar todos los valores relacionados con el resultado por conveniencia. Solo puede usar cinco variables independientes: max, top, left, bottom, right. Simplemente es más fácil asignar en una línea a la matriz y luego la subrutina devuelve la matriz con toda la información necesaria.

Si copia y pega este código en un editor habilitado para resaltar texto con el soporte de Ruby, obviamente lo entenderá mejor. ¡Espero que esto ayude!

Aquí hay una explicación para ir con el código publicado. Hay dos trucos clave para que esto funcione de manera eficiente: (I) el algoritmo de Kadane y (II) el uso de sums de prefijos. También necesitas (III) aplicar los trucos a la matriz.

Parte I: Algoritmo de Kadane

El algoritmo de Kadane es una forma de encontrar una subsecuencia contigua con sum máxima. Comencemos con un enfoque de fuerza bruta para encontrar la subsecuencia máxima contigua y luego consideremos optimizarla para obtener el algoritmo de Kadane.

Supongamos que tiene la secuencia:

 -1, 2, 3, -2 

Para el enfoque de la fuerza bruta, camine a lo largo de la secuencia generando todas las subsecuencias posibles como se muestra a continuación. Teniendo en cuenta todas las posibilidades, podemos comenzar, ampliar o finalizar una lista con cada paso.

 At index 0, we consider appending the -1 -1, 2, 3, -2 ^ Possible subsequences: -1 [sum -1] At index 1, we consider appending the 2 -1, 2, 3, -2 ^ Possible subsequences: -1 (end) [sum -1] -1, 2 [sum 1] 2 [sum 2] At index 2, we consider appending the 3 -1, 2, 3, -2 ^ Possible subsequences: -1, (end) [sum -1] -1, 2 (end) [sum -1] 2 (end) [sum 2] -1, 2, 3 [sum 4] 2, 3 [sum 5] 3 [sum 3] At index 3, we consider appending the -2 -1, 2, 3, -2 ^ Possible subsequences: -1, (end) [sum -1] -1, 2 (end) [sum 1] 2 (end) [sum 2] -1, 2 3 (end) [sum 4] 2, 3 (end) [sum 5] 3, (end) [sum 3] -1, 2, 3, -2 [sum 2] 2, 3, -2 [sum 3] 3, -2 [sum 1] -2 [sum -2] 

Para este enfoque de fuerza bruta, finalmente elegimos la lista con la mejor sum, (2, 3) , y esa es la respuesta. Sin embargo, para que esto sea eficiente, considere que realmente no necesita mantener cada una de las listas. Fuera de las listas que no han terminado, solo necesitas conservar la mejor, los demás no pueden hacerlo mejor. De las listas que han finalizado, es posible que solo necesite conservar la mejor, y solo si es mejor que las que no han finalizado.

Por lo tanto, puede realizar un seguimiento de lo que necesita con solo una matriz de posición y una matriz de sum. La matriz de posición se define así: position[r] = s realiza un seguimiento de la lista que termina en r comienza en s . Y, sum[r] da una sum para la subsecuencia que termina en el index r . Este enfoque optimizado es el algoritmo de Kadane.

Repasando el ejemplo nuevamente, haciendo un seguimiento de nuestro progreso de esta manera:

 At index 0, we consider appending the -1 -1, 2, 3, -2 ^ We start a new subsequence for the first element. position[0] = 0 sum[0] = -1 At index 1, we consider appending the 2 -1, 2, 3, -2 ^ We choose to start a new subsequence because that gives a higher sum than extending. position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 At index 2, we consider appending the 3 -1, 2, 3, -2 ^ We choose to extend a subsequence because that gives a higher sum than starting a new one. position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 position[2] = 1 sum[2] = 5 Again, we choose to extend because that gives a higher sum that starting a new one. -1, 2, 3, -2 ^ position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 position[2] = 1 sum[2] = 5 positions[3] = 3 sum[3] = 3 

De nuevo, la mejor sum es 5 y la lista es del índice 1 al índice 2, que es (2, 3).

Parte II: Sumas de prefijo

Queremos tener una forma de calcular la sum a lo largo de una fila, para cualquier punto de inicio para cualquier punto final. Quiero calcular esa sum en O (1) tiempo en lugar de simplemente sumr, lo que toma O (m) tiempo donde m es el número de elementos en la sum. Con algo de precomputación, esto se puede lograr. Así es cómo. Supongamos que tienes una matriz:

 adg behcfi 

Puede precalcular esta matriz:

 adg a+b d+e g+h a+b+c d+e+f g+h+i 

Una vez hecho esto, puede obtener la sum que se ejecuta a lo largo de cualquier columna desde cualquier punto inicial a punto final en la columna simplemente restando dos valores.

Parte III: Juntar trucos para encontrar la submatriz máxima

Supongamos que conoce la fila superior e inferior de la submatriz máxima. Podrías hacer esto:

  1. Ignora las filas arriba de tu fila superior e ignora las filas debajo de tu fila inferior.
  2. Con la matriz que queda, considere la utilización de la sum de cada columna para formar una secuencia (algo así como una fila que representa múltiples filas). (Puede calcular cualquier elemento de esta secuencia rápidamente con el enfoque de sums de prefijo).
  3. Usa el enfoque de Kadane para descubrir la mejor subsecuencia en esta secuencia. Los índices que obtenga le indicarán las posiciones izquierda y derecha de la mejor submatriz.

Ahora, ¿qué hay de averiguar realmente la fila superior e inferior? Solo prueba todas las posibilidades. Intenta poner la parte superior donde puedas y coloca la parte inferior donde puedas y ejecuta el procedimiento de base Kadane descrito anteriormente para cada posibilidad. Cuando encuentra un máximo, realiza un seguimiento de la posición superior e inferior.

Encontrar la fila y la columna toma O (M ^ 2) donde M es el número de filas. Encontrar la columna toma el tiempo O (N) donde N es el número de columnas. Entonces, el tiempo total es O (M ^ 2 * N). Y, si M = N, el tiempo requerido es O (N ^ 3).

Ya hay muchas respuestas, pero aquí hay otra implementación de Java que escribí. Compara 3 soluciones:

  1. Naïve (fuerza bruta) – O (n ^ 6) tiempo
  2. La solución DP obvia – O (n ^ 4) tiempo y O (n ^ 3) espacio
  3. La solución DP más inteligente basada en el algoritmo de Kadane – O (n ^ 3) tiempo y O (n ^ 2) espacio

Hay ejemplos de ejecuciones para n = 10 a n = 70 en incrementos de 10 con una salida agradable que compara el tiempo de ejecución y los requisitos de espacio.

enter image description here

Código:

 public class MaxSubarray2D { static int LENGTH; final static int MAX_VAL = 10; public static void main(String[] args) { for (int i = 10; i <= 70; i += 10) { LENGTH = i; int[][] a = new int[LENGTH][LENGTH]; for (int row = 0; row < LENGTH; row++) { for (int col = 0; col < LENGTH; col++) { a[row][col] = (int) (Math.random() * (MAX_VAL + 1)); if (Math.random() > 0.5D) { a[row][col] = -a[row][col]; } //System.out.printf("%4d", a[row][col]); } //System.out.println(); } System.out.println("N = " + LENGTH); System.out.println("-------"); long start, end; start = System.currentTimeMillis(); naiveSolution(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms no auxiliary space requirements"); start = System.currentTimeMillis(); dynamicProgammingSolution(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " + ((int) Math.pow(LENGTH, 4)) + " integers"); start = System.currentTimeMillis(); kadane2D(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " + + ((int) Math.pow(LENGTH, 2)) + " integers"); System.out.println(); System.out.println(); } } // O(N^2) !!! public static void kadane2D(int[][] a) { int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!) for (int r = 0; r < LENGTH + 1; r++) { for (int c = 0; c < LENGTH; c++) { s[r][c] = 0; } } for (int r = 1; r < LENGTH + 1; r++) { for (int c = 0; c < LENGTH; c++) { s[r][c] = s[r - 1][c] + a[r - 1][c]; } } int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed! for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed! int[] s1 = new int[LENGTH]; for (int c = 0; c < LENGTH; c++) { s1[c] = s[r2][c] - s[r1 - 1][c]; } int max = 0; int c1 = 0; for (int c = 0; c < LENGTH; c++) { max = s1[c] + max; if (max <= 0) { max = 0; c1 = c + 1; } if (max > maxSum) { maxSum = max; maxRowStart = r1 - 1; maxColStart = c1; maxRowEnd = r2 - 1; maxColEnd = c; } } } } System.out.print("KADANE SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } // O(N^4) !!! public static void dynamicProgammingSolution(int[][] a) { int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width] int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 0; h < LENGTH + 1; h++) { for (int w = 0; w < LENGTH + 1; w++) { dynTable[r][c][h][w] = 0; } } } } for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 1; h <= LENGTH - r; h++) { int rowTotal = 0; for (int w = 1; w <= LENGTH - c; w++) { rowTotal += a[r + h - 1][c + w - 1]; dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w]; } } } } for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 0; h < LENGTH + 1; h++) { for (int w = 0; w < LENGTH + 1; w++) { if (dynTable[r][c][h][w] > maxSum) { maxSum = dynTable[r][c][h][w]; maxRowStart = r; maxColStart = c; maxRowEnd = r + h - 1; maxColEnd = c + w - 1; } } } } } System.out.print(" DP SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } // O(N^6) !!! public static void naiveSolution(int[][] a) { int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int rowStart = 0; rowStart < LENGTH; rowStart++) { for (int colStart = 0; colStart < LENGTH; colStart++) { for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) { for (int colEnd = 0; colEnd < LENGTH; colEnd++) { int sum = 0; for (int row = rowStart; row <= rowEnd; row++) { for (int col = colStart; col <= colEnd; col++) { sum += a[row][col]; } } if (sum > maxSum) { maxSum = sum; maxRowStart = rowStart; maxColStart = colStart; maxRowEnd = rowEnd; maxColEnd = colEnd; } } } } } System.out.print(" NAIVE SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } } 

Aquí hay una versión de Java de la implementación de Ernesto con algunas modificaciones:

 public int[][] findMaximumSubMatrix(int[][] matrix){ int dim = matrix.length; //computing the vertical prefix sum for columns int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[j][i] = matrix[j][i]; } else { ps[j][i] = matrix[j][i] + ps[j - 1][i]; } } } int maxSum = matrix[0][0]; int top = 0, left = 0, bottom = 0, right = 0; //Auxiliary variables int[] sum = new int[dim]; int[] pos = new int[dim]; int localMax; for (int i = 0; i < dim; i++) { for (int k = i; k < dim; k++) { // Kadane over all columns with the i..k rows reset(sum); reset(pos); localMax = 0; //we keep track of the position of the max value over each Kadane's execution // notice that we do not keep track of the max value, but only its position sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]); for (int j = 1; j < dim; j++) { if (sum[j-1] > 0){ sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]); pos[j] = pos[j-1]; }else{ sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]); pos[j] = j; } if (sum[j] > sum[localMax]){ localMax = j; } }//Kadane ends here if (sum[localMax] > maxSum){ /* sum[localMax] is the new max value the corresponding submatrix goes from rows i..k. and from columns pos[localMax]..localMax */ maxSum = sum[localMax]; top = i; left = pos[localMax]; bottom = k; right = localMax; } } } System.out.println("Max SubMatrix determinant = " + maxSum); //composing the required matrix int[][] output = new int[bottom - top + 1][right - left + 1]; for(int i = top, k = 0; i <= bottom; i++, k++){ for(int j = left, l = 0; j <= right ; j++, l++){ output[k][l] = matrix[i][j]; } } return output; } private void reset(int[] a) { for (int index = 0; index < a.length; index++) { a[index] = 0; } } 

Con la ayuda del Algoritmo y Larry y una modificación del Algoritmo de Kadane, aquí está mi solución:

 int dim = matrix.length; //computing the vertical prefix sum for columns int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[j][i] = matrix[j][i]; } else { ps[j][i] = matrix[j][i] + ps[j - 1][i]; } } } int maxSoFar = 0; int min , subMatrix; //iterate over the possible combinations applying Kadane's Alg. for (int i = 0; i < dim; i++) { for (int j = i; j < dim; j++) { min = 0; subMatrix = 0; for (int k = 0; k < dim; k++) { if (i == 0) { subMatrix += ps[j][k]; } else { subMatrix += ps[j][k] - ps[i - 1 ][k]; } if(subMatrix < min){ min = subMatrix; } if((subMatrix - min) > maxSoFar){ maxSoFar = subMatrix - min; } } } } 

Lo único que queda es determinar los elementos de la submatriz, es decir: la esquina superior izquierda e inferior derecha de la submatriz. ¿Alguna sugerencia?

Voy a publicar una respuesta aquí y puedo agregar el código de C ++ real si se solicita porque recientemente he trabajado en esto. Algunos rumores de una división y conquistador que pueden resolver esto en O (N ^ 2) están por ahí, pero no he visto ningún código para apoyar esto. En mi experiencia, lo siguiente es lo que he encontrado.

  O(i^3j^3) -- naive brute force method o(i^2j^2) -- dynamic programming with memoization O(i^2j) -- using max contiguous sub sequence for an array if ( i == j ) O(n^6) -- naive O(n^4) -- dynamic programming O(n^3) -- max contiguous sub sequence 

Echa un vistazo al paquete JAMA ; Creo que hará tu vida más fácil.

Aquí está la solución C #. Ref: http://www.algorithmist.com/index.php/UVa_108

 public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx) { MaxSumMatrix maxSumMtrx = new MaxSumMatrix(); // Step 1. Create SumMatrix - do the cumulative columnar summation // S[i,j] = S[i-1,j]+ inMtrx[i-1,j]; int m = inMtrx.GetUpperBound(0) + 2; int n = inMtrx.GetUpperBound(1)+1; int[,] sumMatrix = new int[m, n]; for (int i = 1; i < m; i++) { for (int j = 0; j < n; j++) { sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j]; } } PrintMatrix(sumMatrix); // Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij for (int x = 0; x < n; x++) { for (int y = x; y < n; y++) { int[] r_ij = new int[n]; for (int k = 0; k < n; k++) { r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k]; } // Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum => // capture Sum, colStartIdx, ColEndIdx. // capture current x as rowTopIdx, y as rowBottomIdx. MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij); if (currMaxSum.maxSum > maxSumMtrx.sum) { maxSumMtrx.sum = currMaxSum.maxSum; maxSumMtrx.colStart = currMaxSum.maxStartIdx; maxSumMtrx.colEnd = currMaxSum.maxEndIdx; maxSumMtrx.rowStart = x; maxSumMtrx.rowEnd = y; } } } return maxSumMtrx; } public static void PrintMatrix(int[,] matrix) { int endRow = matrix.GetUpperBound(0); int endCol = matrix.GetUpperBound(1); PrintMatrix(matrix, 0, endRow, 0, endCol); } public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol) { StringBuilder sb = new StringBuilder(); for (int i = startRow; i <= endRow; i++) { sb.Append(Environment.NewLine); for (int j = startCol; j <= endCol; j++) { sb.Append(string.Format("{0} ", matrix[i,j])); } } Console.WriteLine(sb.ToString()); } // Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum public static MaxSum FindMaxSumSubarray(int[] inArr) { int currMax = 0; int currStartIndex = 0; // initialize maxSum to -infinity, maxStart and maxEnd idx to 0. MaxSum mx = new MaxSum(int.MinValue, 0, 0); // travers through the array for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++) { // add element value to the current max. currMax += inArr[currEndIndex]; // if current max is more that the last maxSum calculated, set the maxSum and its idx if (currMax > mx.maxSum) { mx.maxSum = currMax; mx.maxStartIdx = currStartIndex; mx.maxEndIdx = currEndIndex; } if (currMax < 0) // if currMax is -ve, change it back to 0 { currMax = 0; currStartIndex = currEndIndex + 1; } } return mx; } struct MaxSum { public int maxSum; public int maxStartIdx; public int maxEndIdx; public MaxSum(int mxSum, int mxStart, int mxEnd) { this.maxSum = mxSum; this.maxStartIdx = mxStart; this.maxEndIdx = mxEnd; } } class MaxSumMatrix { public int sum = int.MinValue; public int rowStart = -1; public int rowEnd = -1; public int colStart = -1; public int colEnd = -1; } 

esta es mi implementación del algoritmo 2D Kadane. Creo que es más claro. El concepto se basa solo en el algoritmo kadane. El primer y segundo bucle de la parte principal (que está en la parte inferior del código) es seleccionar cada combinación de las filas y el tercer bucle es usar el algoritmo 1D kadane por cada sum de columna siguiente (que se puede calcular en tiempo constante porque de preprocesamiento de matriz restando valores de dos filas recogidas (de combinación)). Aquí está el código:

  int [][] m = { {1,-5,-5}, {1,3,-5}, {1,3,-5} }; int N = m.length; // summing columns to be able to count sum between two rows in some column in const time for (int i=0; i 

Aquí está mi solución. Es O (n ^ 3) en el tiempo y O (n ^ 2) espacio. https://gist.github.com/toliuweijing/6097144

 // 0th O(n) on all candidate bottoms @B. // 1th O(n) on candidate tops @T. // 2th O(n) on finding the maximum @left/@right match. int maxRect(vector >& mat) { int n = mat.size(); vector >& colSum = mat; for (int i = 1 ; i < n ; ++i) for (int j = 0 ; j < n ; ++j) colSum[i][j] += colSum[i-1][j]; int optrect = 0; for (int b = 0 ; b < n ; ++b) { for (int t = 0 ; t <= b ; ++t) { int minLeft = 0; int rowSum[n]; for (int i = 0 ; i < n ; ++i) { int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i]; rowSum[i] = i == 0? col : col + rowSum[i-1]; optrect = max(optrect, rowSum[i] - minLeft); minLeft = min(minLeft, rowSum[i]); } } } return optrect; } 

Me gustaría analizar el conjunto de NxN eliminando el -ves lo que queda es la sum más alta de una matriz secundaria.

La pregunta no dice que debe dejar intacta la matriz original o que el orden importa.