algoritmo kadane con divide y venceras?

[Tordur]

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

Código (java) [Seleccionar] Expandir

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

[srWhiteSkull]

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/