Maximum Sum Rectangle
Updated
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[][]) → longExamples
Example 1
matrix = [[1,2,-1,-4,-20],[-8,-3,4,2,1],[3,8,10,1,3],[-4,-1,1,7,-6]]return = 29The 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 = -1Every rectangle has a negative sum. The best non-empty rectangle contains only -1.
Example 3
matrix = [[2,-1,2,3,-9]]return = 6In the single row, the contiguous range [2,-1,2,3] sums to 6.
Constraints
1 <= matrix.length <= 751 <= 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