FastPrepMaximum Sum Rectangle
Problems/Maximum Sum Rectangle

Maximum Sum Rectangle

Deloitte logoDeloitte● HardNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Deloitte new grad online assessment. The report names the maximum-sum rectangle task and gives the goal for the matrix. We make clear that the rectangle must not be empty, and use limits that work in every language. Our version is about 98% the same as the reported question.

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
matrix
01234012-1-4-201-8-342123810133-4-117-6

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
matrix
010-3-41-1-2

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

Example 3

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

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 Online Assessment questions

  • Seventh Nearest PalindromeOA · Seen May 2026
  • Minimum Deletions for a Non-PalindromeOA · Seen Jul 2025
  • Minimum-Cost Solar Rooftop AllocationOA · Seen Jul 2025
  • Pair Elements with Even SumsOA · Seen Jul 2025
  • Count Divisible PermutationsOA · Seen Jan 2025
  • Largest Element in an ArrayOA · Seen Nov 2024
  • Install Carbon FiltersOA · Seen Oct 2023
  • Longest Substring with Even OccurrencesOA · Seen Oct 2023
  • Annual Bank Balance with Monthly Card FeesOA · Seen Jan 2022
  • Count Battleships by SizeOA · Seen Jan 2022

Similar questions at other companies

  • Cherry PickupInfosys · OAInfosys interview questions
  • Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
  • Maximize CollaborationTikTok · OATikTok interview questions
  • Timed Coin Collection in a 2×N GridAtlassian · OAAtlassian interview questions
  • Largest Square of OnesOpenAI · OAOpenAI interview questions
  • Shortest Path Around Rectangular ObstaclesDRW · OADRW interview questions
  • Largest Plus SignxAI · OAxAI interview questions
  • Minimize Sum of Distances to WarehousesAmazon · OA
  • Largest Square Sub-Grid Within a Sum LimitC3.ai · OAC3.ai interview questions
  • Maximum Apples from Two Disjoint Fixed-Length SegmentsMarshall Wace · OAMarshall Wace interview questions

Interview reports that mention this question

  • Deloitte New Grad Tech OA and Interview Questions: 14 Experiences
All Deloitte interview questionsSee Deloitte hiring insights
Saved
class Solution {
    public long maximumSumRectangle(int[][] matrix) {
        // Write your solution here.
    }
}
Checking account…