Finding the maximum sum rectangle in a 2D array.

Here’s an example of a Java program that solves the problem of finding the maximum sum rectangle in a 2D array:

   public class MaximumSumRectangle {


    public static void main(String[] args) {

        int[][] matrix = {

            { 1, 2, -1, -4, -20 },

            { -8, -3, 4, 2, 1 },

            { 3, 8, 10, 1, 3 },

            { -4, -1, 1, 7, -6 }

        };
    
        int maxSum = findMaxSumRectangle(matrix);

        System.out.println("Maximum sum of rectangle: " + maxSum);

    }

    public static int findMaxSumRectangle(int[][] matrix) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        // Variables to store the final result

        int maxSum = Integer.MIN_VALUE;

        int leftBound = 0;

        int rightBound = 0;

        int topBound = 0;

        int bottomBound = 0;

        // Variables for intermediate calculations

        int[] temp = new int[rows];

        int currentSum;

        int currentLeftBound;

        int currentRightBound;

        // Iterate over all possible left columns

        for (int left = 0; left < cols; left++) {

            // Reset the temporary array

            for (int i = 0; i < rows; i++) {

                temp[i] = 0;

            }

            // Iterate over all possible right columns

            for (int right = left; right < cols; right++) {

                // Update the temporary array by adding the corresponding column values

                for (int i = 0; i < rows; i++) {

                    temp[i] += matrix[i][right];

                }

                // Find the maximum subarray sum in the temporary array

                KadaneResult kadaneResult = kadane(temp);

                currentSum = kadaneResult.maxSum;

                currentLeftBound = left;

                currentRightBound = right;

                // Update the final result if the current sum is greater

                if (currentSum > maxSum) {

                    maxSum = currentSum;

                    leftBound = currentLeftBound;

                    rightBound = currentRightBound;

                    topBound = kadaneResult.startIndex;

                    bottomBound = kadaneResult.endIndex;
               }
            }
        }

        // Print the maximum sum rectangle

        System.out.println("Maximum sum rectangle:");

        for (int i = topBound; i <= bottomBound; i++) {

            for (int j = leftBound; j <= rightBound; j++) {

                System.out.print(matrix[i][j] + " ");

            }

            System.out.println();

        }

        return maxSum;

    }

    public static KadaneResult kadane(int[] arr) {

        int maxSoFar = Integer.MIN_VALUE;

        int maxEndingHere = 0;

        int startIndex = 0;

        int endIndex = -1;

        int currentStart = 0;

        for (int i = 0; i < arr.length; i++) {

            maxEndingHere += arr[i];

            if (maxEndingHere < 0) {

                maxEndingHere = 0;

                currentStart = i + 1;

            } else if (maxEndingHere > maxSoFar) {

                maxSoFar = maxEndingHere;

                startIndex = currentStart;

                endIndex = i;

            }
        }

        return new KadaneResult(maxSoFar, startIndex, endIndex);

    }

    public static class

  KadaneResult {

        int maxSum;

        int startIndex;

        int endIndex;

        public KadaneResult(int maxSum, int startIndex, int endIndex) {

            this.maxSum = maxSum;

            this.startIndex = startIndex;

            this.endIndex = endIndex;

        }
    }
}

In this example, the `findMaxSumRectangle` method takes a 2D matrix as input and returns the maximum sum of a rectangle within the matrix. The program uses the Kadane’s algorithm to find the maximum subarray sum in each column combination. It keeps track of the maximum sum and the bounds of the rectangle that achieves that sum. Finally, it prints the maximum sum rectangle.

You can modify the `matrix` variable to test the program with different 2D arrays.