Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement