- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a 2d matrix and another value k, we have to find the largest sum of a rectangle where sum ≤ k.

So, if the input is like

5 | −2 |

7 | 10 |

and k = 15, then the output will be 12, as we can take the rectangle [5, 7] to get sum of 12 less than 15.

To solve this, we will follow these steps −

n := row count of a

m := column count of a

ans := inf

for i1 in range 0 to n, do

row := a list of size m and fill with 0

for i2 in range i1 to n, do

for j in range 0 to m, do

row[j] := row[j] + a[i2, j]

s := a new set

insert 0 into s

sum := 0

for j in range 0 to m, do

sum := sum + row[j];

temp := a list for all items in s which is larger than (sum − k)

if size of temp > 0, then

u := minimum of temp

ans := maximum of ans and (sum − u)

insert sum into s

return ans

Let us see the following implementation to get better understanding −

class Solution: def solve(self, a, k): n = len(a) if n == 0: return 0; m = len(a[0]) ans = -999999; for i1 in range(n): row = [0]*m; for i2 in range(i1, n): for j in range(m): row[j] += a[i2][j] s = set() s.add(0) sum = 0 for j in range(m): sum += row[j]; temp = [e for e in s if e > (sum − k)] if len(temp) > 0: u = min(temp) ans = max(ans, sum − u) s.add(sum) return ans ob = Solution() matrix = [ [5, −2], [7, 10] ] k = 15 print(ob.solve(matrix, k))

[ [5, −2], [7, 10] ], 15

12

- Related Questions & Answers
- Program to find maximum sum by performing at most k negate operations in Python
- Program to find sum of k non-overlapping sublists whose sum is maximum in C++
- Program to find a sub-list of size at least 2 whose sum is multiple of k in Python
- Program to find size of smallest sublist whose sum at least target in Python
- Program to count number of paths whose sum is k in python
- Program to find number of consecutive subsequences whose sum is divisible by k in Python
- Program to find three unique elements from list whose sum is closest to k Python
- Program to Find K-Largest Sum Pairs in Python
- Program to find largest average of sublist whose size at least k in Python
- Program to find the sum of largest K sublist in Python
- Program to find sum of digits in base K using Python
- Program to find max number of K-sum pairs in Python
- Program to find the sum of the lengths of two nonoverlapping sublists whose sum is given in Python
- Program to find number of sequences after adjacent k swaps and at most k swaps in Python
- Program to find product of few numbers whose sum is given in Python

Advertisements