Foro de elhacker.net

Buenas,
tenia pensado intentar hacer el algoritmo de kadane para submatrices, pero solo lo he encontrado con programacion dinamica.

He intentado hacerlo de todos modos, pero me sigue sin salir, ya que por alguna razon el pivote que uso no lo termina cogiendo bien y no obtiene una matriz de maximo.

Os dejo el codigo por aqui:
https://pastebin.com/rspA8iWE (https://pastebin.com/rspA8iWE)

public static int maxSuma2D(int[][] matriz) {
    	//funcion para llamar al algoritmo    
		return maxSubarrayAux2D(matriz ,0 ,0 ,matriz.length-1 ,matriz[0].length-1 );
    }
 
static int maxSubarrayAux2D(int[][] matriz, int i0, int j0, int iN, int jN){
		//fase dividir
		if(i0 >= iN || j0 >= jN){
			return matriz[i0][j0] ;
        }
        else{
            int ik=(i0+iN)/2;
            int jk=(j0+jN)/2;
            int m1 = maxSubarrayAux2D(matriz, i0, j0, ik, jk);
            int m2 = maxSubarrayAux2D(matriz, ik+1, j0, iN, jk);
            int m3 = maxSubarrayAux2D(matriz, i0, jk+1, ik, jN);
            int m4 = maxSubarrayAux2D(matriz, ik+1, jk+1, iN, jN);
            int m5 = maxSubarrayCruzada2D(matriz, i0, j0, ik, jk, iN, jN);
            return Math.max(m1,Math.max(m2,Math.max(m3,Math.max(m4,m5))));
        }
    }
    static int maxSubarrayCruzada2D(int[][] matriz, int i0, int ik, int iN, int j0, int jk, int jN){
        //fase conquistar
		int max = Integer.MIN_VALUE;
        int suma = 0;
        int suma2 = 0;
        int suma3 = 0;
        int suma4 = 0;
        for (int i = ik; i >= i0; i--) {
            for(int j = jk; j >= j0; j--) {
                suma += matriz[i][j];
                if (suma > max) max = suma;
            }
        }
        for (int i = ik + 1; i <= iN; i++) {
            for(int j = jk; j >= j0; j--) {
                suma2 += matriz[i][j];
                if (suma2 > max) max = suma2;
            }
        }
        for (int i = ik; i >= i0; i--) {
            for(int j = jk + 1; j <= jN; j++) {
                suma3 += matriz[i][j];
                if (suma3 > max) max = suma3;
            }
        }
        for (int i = ik + 1; i <= iN; i++) {
            for(int j = jk + 1; j <= jN; j++) {
                suma4 += matriz[i][j];
                if (suma4 > max) max = suma4;
            }
        }
        max=suma;
        if(suma + suma2 > max)max = suma + suma2;
        if(suma + suma3 > max)max = suma + suma3;
        if(suma2 + suma4 > max)max = suma2 + suma4;
        if(suma3 + suma4 > max)max = suma3 + suma4;
        if(suma + suma2 + suma3 + suma4 > max)max = suma + suma2 + suma3 + suma4;
        return max;
    }

Si alguien sabe como hacerlo, o que error tiene mi codigo lo agradeceria :D

Aquí lo tienes en Java y en un par de lenguajes más, con su explicación paso a paso :

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/