Hourglass problem in Java

In this section, we will discuss the hourglass problem in Java.The aim is to find the largest sum of an hour glass given a 2D matrix.

An hour glass is made up of seven cells arranged in the following pattern.
    A B C
      D
    E F G

Examples:

Input : 1 1 1 0 0 
            0 1 0 0 0 
            1 1 1 0 0 
            0 0 0 0 0 
            0 0 0 0 0 
Output : 7
The hour glass below shows the maximum amount:
1 1 1 
  1
1 1 1
Input : 0 3 0 0 0
           0 1 0 0 0
           1 1 1 0 0
           0 0 2 4 4
           0 0 0 2 4
Output : 11
The hour glass below shows the maximum amount:
1 0 0
  4
0 2 4

Approach:

The concept of the hourglass implies that the number of rows and columns must be equal to three. We may say that counting the total number of hourglasses in a matrix equals counting the number of potential top left cells in an hourglass. In an hourglass, the number of top-left cells equals (R-2)*(C-2). As a result, the total number of hourglasses in a matrix is (R-2)*(C-2).

mat[][] = 2 3 0 0 0 
          0 1 0 0 0
          1 1 1 0 0 
          0 0 2 4 4
          0 0 0 2 0
Possible hour glass are :
2 3 0  3 0 0   0 0 0  
  1      0       0 
1 1 1  1 1 0   1 0 0 


0 1 0  1 0 0  0 0 0 
  1      1      0  
0 0 2  0 2 4  2 4 4 


1 1 1  1 1 0  1 0 0
  0      2      4
0 0 0  0 0 2  0 2 0

Consider each top left cell of an hourglass one at a time. We compute the sum of the hourglass created by each cell. Finally, return the highest sum.

The below is an implementation of the following concept:

Hourglass.java

// Java application for determining the maximum
// hour glass sum in matrix
import java.io.*;
class Hourglass {	
static int R = 5;
static int C = 5;
// Returns the greatest possible sum of
// ar[][] hour glass
static int findMaxSum(int [][]mat)
{
	if (R < 3 || C < 3){
		System.out.println("Not possible");
		System.exit(0);
	}
	//The loop is executed here (R-2)*(C-2)
	// considering several situations
	// hourglass cells in the upper left.
	int max_sum = Integer.MIN_VALUE;
	for (int u = 0; u < R - 2; u++)
	{
		for (int v = 0; v < C - 2; v++)
		{
			// Using mat[u][v] as a benchmark
			// The hour glass's left cell.
			int sum = (mat[u][v] + mat[u][v + 1] +
					mat[u][v + 2]) + (mat[u + 1][v + 1]) +
					(mat[u + 2][v] + mat[u + 2][v + 1] +
					mat[u + 2][v + 2]);
			// If the previous total is less than
			// then update the current total
			// new total in max_sum
			max_sum = Math.max(max_sum, sum);
		}
	}
	return max_sum;
}
	// Driver code
	static public void main (String[] args)
	{
		int [][]mat = {{1, 2, 3, 0, 0},
					{0, 0, 0, 0, 0},
					{2, 1, 4, 0, 0},
					{0, 0, 0, 0, 0},
					{1, 1, 0, 1, 0}};
		int res = findMaxSum(mat);
		System.out.println("Hour glass maximum sum = "+ res);
	}	
}

Output:

Hourglass.java

import java.util.*;
class Hourglass
{
  public static void main(String[]args)
  {
    Scanner scan = new Scanner(System.in);
    System.out.print("The number of rows: ");
    int rows = scan.nextInt();    
    System.out.print("The number of columns: ");
    int columns = scan.nextInt();
    int[][]matrix = new int[rows][columns];
    System.out.println("Enter the Matrix components: ");    
    for(int u = 0; u < rows; u++)
    {
      for(int v = 0; v < columns; v++)
      {
        matrix[u][v]=scan.nextInt();
      }
    }
    int sum = 0,max = 0;
    for(int u = 0; u < rows - 2; u++)
    {
      for(int v = 0; v < columns - 2; v++)
      {
        sum = (matrix[u][v] + matrix[u][v + 1] + matrix[u][v + 2]) + (matrix[u + 1][v + 1]) + (matrix[u + 2][v] + matrix[u + 2][v + 1] + matrix[u + 2][v + 2]);       
        if(sum > max)
        {
          max = sum;
        }
      }
    }
    System.out.println("The largest amount in the hourglass is: "+max);
  }
}

Output: