algorithm - programming - max sum subarray
Obtener la submatriz con suma máxima? (11)
Acerca de la recuperación de la submatriz real, y no solo la suma 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!
Entrada : una matriz bidimensional NxN - Matriz - con elementos positivos y negativos.
Salida : Una submatriz de cualquier tamaño, de modo que su suma 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 suma, a continuación, en Java.
Gracias a Ernesto que logró resolver el resto del problema que está determinando los límites de la matriz, es decir, las esquinas superior izquierda, inferior derecha, a continuación en Ruby.
Aquí está la solución C #. Ref: Algorithmist
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;
}
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<vector<int> >& mat) {
int n = mat.size();
vector<vector<int> >& 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;
}
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 sumas 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 suma 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 suma, (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 suma. 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 suma 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 suma 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 suma a lo largo de una fila, para cualquier punto de inicio para cualquier punto final. Quiero calcular esa suma en O (1) tiempo en lugar de simplemente sumar, lo que toma O (m) tiempo donde m es el número de elementos en la suma. Con algo de precomputación, esto se puede lograr. Así es cómo. Supongamos que tienes una matriz:
a d g
b e h
c f i
Puede precalcular esta matriz:
a d g
a+b d+e g+h
a+b+c d+e+f g+h+i
Una vez hecho esto, puede obtener la suma 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:
- Ignora las filas arriba de tu fila superior e ignora las filas debajo de tu fila inferior.
- Con la matriz que queda, considere la utilización de la suma 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 sumas de prefijo).
- 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).
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 Algorithmist 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?
Echa un vistazo al paquete JAMA ; Creo que hará tu vida más fácil.
Me gustaría analizar el conjunto de NxN eliminando el -ves lo que queda es la suma más alta de una matriz secundaria.
La pregunta no dice que debe dejar intacta la matriz original o que el orden importa.
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
Ya hay muchas respuestas, pero aquí hay otra implementación de Java que escribí. Compara 3 soluciones:
- Naïve (fuerza bruta) - O (n ^ 6) tiempo
- La solución DP obvia - O (n ^ 4) tiempo y O (n ^ 3) espacio
- 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.
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 + ")");
}
}
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 suma 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<N; ++i)
m[0][i] = m[0][i];
for (int j=1; j<N; ++j)
for (int i=0; i<N; ++i)
m[j][i] = m[j][i] + m[j-1][i];
int total_max = 0, sum;
for (int i=0; i<N; ++i) {
for (int k=i; k<N; ++k) { //for each combination of rows
sum = 0;
for (int j=0; j<N; j++) { //kadane algorithm for every column
sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
total_max = Math.max(sum, total_max);
}
}
}
System.out.println(total_max);