FastPrepMaximum Sum Rectangle
Problem · Array

Maximum Sum Rectangle

Learn this problem
● HardDeloitte logoDeloitteNEW GRADOA

Problem statement

You are given a non-empty integer matrix matrix. A rectangle is any non-empty contiguous range of rows combined with any non-empty contiguous range of columns.

Return the maximum possible sum of all values inside one such rectangle.

Function

maximumSumRectangle(matrix: int[][]) → long

Examples

Example 1

matrix = [[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]]return = 29

The rectangle spanning rows 1 through 3 and columns 1 through 3 has sum 29, which is optimal.

Example 2

matrix = [[-3,-4],[-1,-2]]return = -1

Every rectangle has a negative sum. The best non-empty rectangle contains only -1.

Example 3

matrix = [[2,-1,2,3,-9]]return = 6

In the single row, the contiguous range [2,-1,2,3] sums to 6.

Constraints

  • 1 <= matrix.length <= 75
  • 1 <= matrix[i].length <= 75
  • Every row has the same length.
  • -100000 <= matrix[i][j] <= 100000

More Deloitte problems

drafts saved locally
public long maximumSumRectangle(int[][] matrix) {
    // Write your solution here.
}
matrix[[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]]
expected29
checking account