package com.microsoft;

public class MatrixUtil {
  public static long returnSumOfMaxSubMatrix(int[][] matrix) throws Exception {
    int [][]index=new int[4][2];
    index[0]=new int[]{0,0};
    index[1]=new int[]{0,matrix[0].length-1};
    index[2]=new int[]{matrix.length-1,0};
    index[3]=new int[]{matrix.length-1,matrix[0].length-1};
    
    
    return recuisiveMaxSubMatrix(index,matrix);
  }
  
  private static long recuisiveMaxSubMatrix(int[][] index,int[][] matrix){
    if(index[0][0]==index[3][0]&&index[0][1]==index[3][1]){
      return matrix[index[0][0]][index[0][1]];
    }
    int [][]topLeft=new int[4][2];
    topLeft[0]=index[0];
    topLeft[1]=new int[]{index[0][0],(index[0][1]+index[1][1])/2};
    topLeft[2]=new int[]{(index[0][0]+index[2][0])/2,index[0][1]};
    topLeft[3]=new int[]{(index[0][0]+index[2][0])/2,(index[0][1]+index[1][1])/2};
    int [][]topRight=new int[4][2];
    topRight[0]=new int[]{index[0][0],(index[0][1]+index[1][1])/2+1};
    topRight[1]=new int[]{index[1][0],index[1][1]};
    topRight[2]=new int[]{(index[0][0]+index[2][0])/2,(index[0][1]+index[1][1])/2+1};
    topRight[3]=new int[]{(index[0][0]+index[2][0])/2,index[1][1]};
    int [][]bottomLeft=new int[4][2];
    bottomLeft[0]=new int[]{(index[0][0]+index[2][0])/2+1,index[0][1]};
    bottomLeft[1]=new int[]{(index[0][0]+index[2][0])/2+1,(index[0][1]+index[1][1])/2};
    bottomLeft[2]=index[2];
    bottomLeft[3]=new int[]{index[2][0],(index[2][1]+index[3][1])/2};
    int [][]bottomRight=new int[4][2];
    bottomRight[0]=new int[]{(index[0][0]+index[2][0])/2+1,(index[0][1]+index[1][1])/2+1};
    bottomRight[1]=new int[]{(index[0][0]+index[2][0])/2+1,index[1][1]};
    bottomRight[2]=new int[]{index[2][0],(index[2][1]+index[3][1])/2+1};
    bottomRight[3]=index[3];
    long max1=recuisiveMaxSubMatrix(topLeft,matrix);
    long max2=recuisiveMaxSubMatrix(topRight,matrix);
    long max3=recuisiveMaxSubMatrix(bottomLeft,matrix);
    long max4=recuisiveMaxSubMatrix(bottomRight,matrix);
    long maxTop=Integer.MIN_VALUE;
    long max=0;
  
    for(int x1=topLeft[0][0];x1<=topLeft[2][0];x1++){
      for(int x2=x1;x2<=topLeft[2][0];x2++){
        for(int y1=topLeft[0][1];y1<=topLeft[1][1];y1++){
          for(int y2=topRight[0][1];y2<=topRight[1][1];y2++){
            max=0;
            for(int i=x1;i<=x2;i++){
              for(int j=y1;j<=y2;j++){
                max+=matrix[i][j];
              }
            }
            maxTop=Math.max(maxTop, max);
          }
        }
      }
    }
    
    long maxLeft=Long.MIN_VALUE;
    max=0;
    for(int x1=topLeft[0][0];x1<=topLeft[2][0];x1++){
      for(int x2=bottomLeft[0][0];x2<=bottomLeft[2][0];x2++){
        for(int y1=topLeft[0][1];y1<=topLeft[1][1];y1++){
          for(int y2=y1;y2<=topLeft[1][1];y2++){
            max=0;
            for(int i=x1;i<=x2;i++){
              for(int j=y1;j<=y2;j++){
                max+=matrix[i][j];
              }
            }
            maxLeft=Math.max(maxLeft, max);
          }
        }
      }
    }
    long maxBottom=Long.MIN_VALUE;
    max=0;
    for(int x1=bottomLeft[0][0];x1<=bottomLeft[2][0];x1++){
      for(int x2=x1;x2<=bottomLeft[2][0];x2++){
        for(int y1=bottomLeft[0][1];y1<=bottomLeft[1][1];y1++){
          for(int y2=bottomRight[0][1];y2<=bottomRight[1][1];y2++){
            max=0;
            for(int i=x1;i<=x2;i++){
              for(int j=y1;j<=y2;j++){
                max+=matrix[i][j];
              }
            }
            maxBottom=Math.max(maxBottom, max);
          }
        }
      }
    }
    
    long maxRight=Long.MIN_VALUE;
    max=0;
    for(int x1=topRight[0][0];x1<=topRight[2][0];x1++){
      for(int x2=bottomRight[0][0];x2<=bottomRight[2][0];x2++){
        for(int y1=bottomRight[0][1];y1<=bottomRight[1][1];y1++){
          for(int y2=y1;y2<=bottomRight[1][1];y2++){
            max=0;
            for(int i=x1;i<=x2;i++){
              for(int j=y1;j<=y2;j++){
                max+=matrix[i][j];
              }
            }
            maxRight=Math.max(maxRight, max);
          }
        }
      }
    }
    
    long maxFull=Long.MIN_VALUE;
    max=0;
    for(int x1=topLeft[0][0];x1<=topLeft[2][0];x1++){
      for(int x2=bottomLeft[0][0];x2<=bottomLeft[2][0];x2++){
        for(int y1=bottomLeft[0][1];y1<=bottomLeft[1][1];y1++){
          for(int y2=bottomRight[0][1];y2<=bottomRight[1][1];y2++){
            max=0;
            for(int i=x1;i<=x2;i++){
              for(int j=y1;j<=y2;j++){
                max+=matrix[i][j];
              }
            }
            maxFull=Math.max(maxFull, max);
          }
        }
      }
    }
    
    long result=Math.max(max1, max2);
    result=Math.max(result, max3);
    result=Math.max(result, max4);
    result=Math.max(result, maxTop);
    result=Math.max(result, maxLeft);
    result=Math.max(result, maxBottom);
    result=Math.max(result, maxRight);
    result=Math.max(result, maxFull);
    return result;
    
  }

  public static void main(String[] args) throws Exception {
    int[][] matrix = { { 9, -3, 7, -5 }, { -3, -4, 2, 0 }, { 7, 2, 2, -1 },
        { -5, 0, -1, 6 } };
    long max = returnSumOfMaxSubMatrix(matrix);
    System.out.println("Max = " + max);
  }
}