Advertisement
Guest User

kadane 2D divide and conquer

a guest
Oct 21st, 2018
259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.21 KB | None | 0 0
  1. public static int maxSuma2D(int[][] matriz) {
  2. //funcion para llamar al algoritmo
  3. return maxSubarrayAux2D(matriz ,0 ,0 ,matriz.length-1 ,matriz[0].length-1 );
  4. }
  5.  
  6. static int maxSubarrayAux2D(int[][] matriz, int i0, int j0, int iN, int jN){
  7. //fase dividir
  8. if(i0 >= iN || j0 >= jN){
  9. return matriz[i0][j0] ;
  10. }
  11. else{
  12. int ik=(i0+iN)/2;
  13. int jk=(j0+jN)/2;
  14. int m1 = maxSubarrayAux2D(matriz, i0, j0, ik, jk);
  15. int m2 = maxSubarrayAux2D(matriz, ik+1, j0, iN, jk);
  16. int m3 = maxSubarrayAux2D(matriz, i0, jk+1, ik, jN);
  17. int m4 = maxSubarrayAux2D(matriz, ik+1, jk+1, iN, jN);
  18. int m5 = maxSubarrayCruzada2D(matriz, i0, j0, ik, jk, iN, jN);
  19. return Math.max(m1,Math.max(m2,Math.max(m3,Math.max(m4,m5))));
  20. }
  21. }
  22. static int maxSubarrayCruzada2D(int[][] matriz, int i0, int ik, int iN, int j0, int jk, int jN){
  23. //fase conquistar
  24. int max = Integer.MIN_VALUE;
  25. int suma = 0;
  26. int suma2 = 0;
  27. int suma3 = 0;
  28. int suma4 = 0;
  29. for (int i = ik; i >= i0; i--) {
  30. for(int j = jk; j >= j0; j--) {
  31. suma += matriz[i][j];
  32. if (suma > max) max = suma;
  33. }
  34. }
  35. for (int i = ik + 1; i <= iN; i++) {
  36. for(int j = jk; j >= j0; j--) {
  37. suma2 += matriz[i][j];
  38. if (suma2 > max) max = suma2;
  39. }
  40. }
  41. for (int i = ik; i >= i0; i--) {
  42. for(int j = jk + 1; j <= jN; j++) {
  43. suma3 += matriz[i][j];
  44. if (suma3 > max) max = suma3;
  45. }
  46. }
  47. for (int i = ik + 1; i <= iN; i++) {
  48. for(int j = jk + 1; j <= jN; j++) {
  49. suma4 += matriz[i][j];
  50. if (suma4 > max) max = suma4;
  51. }
  52. }
  53. max=suma;
  54. if(suma + suma2 > max)max = suma + suma2;
  55. if(suma + suma3 > max)max = suma + suma3;
  56. if(suma2 + suma4 > max)max = suma2 + suma4;
  57. if(suma3 + suma4 > max)max = suma3 + suma4;
  58. if(suma + suma2 + suma3 + suma4 > max)max = suma + suma2 + suma3 + suma4;
  59. return max;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement