Last Updated: 4 Dec, 2021

Maximum Sum No Larger Than K

Hard

Asked in companies

Solve now

Problem statement

You are given an ‘N’ x ‘M’ matrix ‘MAT’ and an integer ‘K’. Your task is to find the maximum sum of a rectangle in the matrix which is less than or equal to ‘K’.

For Example:

You are given ‘MAT’= [[1, 2],[3, 4]] and ‘K’ = 8.

Then the answer will be 7 (the sum of the red rectangle).

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains three space-separated integers, ‘N’ and ‘M’ representing the number of rows and columns in ‘MAT’, respectively, and ‘K’.

The next ‘N’ lines contain ‘M’ space-separated integers representing the elements of ‘MAT’.

Output Format:

For each test case, print the maximum sum of a rectangle in the matrix which is less than or equal to ‘K’

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
-10^6 <= K <= 10^6
-10^6 <= MAT[i][j] <= 10^6

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Prerequisite: Subarray sum equals K

In this approach, we will first calculate the prefix sum of each row. We will use the input matrix itself to store the prefix sum of each row. We will get the range sum for every two columns using the subtraction of the prefix sum. Then for every index ‘X’, we will store the prefix sums in a sorted container. Now, to find the maximum possible sum which is less than or equal to ‘K’, we will find if there is a possible sub-array with sum ‘K’ that ends at ‘X’ and if not, will try to find the sum with possible sum k -1 and so on.

Algorithm :

Initialize a variable ‘ANS’ with the minimum integer value.
Iterate ‘I’ in 0 to ‘N’:
- Iterate ‘J’ in 1 to ‘M’:
  - Set ‘MAT’[‘I’][‘J’] as ‘MAT’[‘X’][‘J’] + ‘MAT’[‘X’][‘I’ - 1].
Iterate ‘I’ in 0 to ‘M’:
- Iterate ‘J’ in ‘I’ to ‘M’:
  - Initialize a sorted container ‘SET’.(set in c++, TreeSet in java, SortedSet in python).
  - Add 0 to ‘SET’.
  - Set ‘SUM’ as 0.
  - Iterate ‘X’ in 0 to ‘N’:
    - If ‘I’ is greater than 0, add (‘MAT’[‘X’][‘J’] - ‘MAT’[‘X’][‘I’ - 1] to ‘SUM’, otherwise, add ‘MAT’[‘X’][‘J’] to ‘SUM’.
    - Set ‘VAL’ as CEIL(’SET’[‘SUM’ - ‘K’]).
    - If ‘VAL’ is not null.
      - Set ‘ANS’ as the maximum value of ‘ANS’ and ‘SUM’ - ‘VAL’.
    - Add ‘SUM’ to ‘SET’.
Return ‘ANS’.

Solve now

02 Approach

Prerequisite: Kadane’s algorithm

Kadane’s algorithm is used to find a maximum sum contiguous subarray within a one-dimensional numeric array in O(N) time. In this approach, we will create an integer array that will store the prefix sums of each row from column i to j where 0 < ‘I’ < ‘J’ < ‘M’. We will run Kadane’s algorithm on each such array to get the maximum possible sum closest to ‘K’ of any subarray of it in the same way as we have done in approach 1.

Algorithm :

Initialize a variable ‘ANS’ with the minimum integer value.
Iterate ‘LEFTCOL’ in 0 to ‘M’:
- Initialize an integer array ‘ROWSUM’.
- Iterate ‘RIGHTCOL’ in ‘LEFTCOL’ to ‘M’:
  - Iterate ‘ROW’ in 0 to ‘N’:
    - Add ‘MAT’[‘ROW’][‘RIGHTCOL’] to ‘ROWSUM’[‘ROW’].
  - Initialize a sorted container ‘SET’.
  - Add 0 to ‘SET’.
  - Set ‘CSUM’ as 0.
  - Iterate ‘A’ in ‘ROWSUM’:
    - Add ‘A’ to ‘CSUM’.
    - Set ‘VAL’ as CEIL(’SET’[C‘SUM’ - ‘K’]).
    - If ‘VAL’ is not null.
      - Set ‘ANS’ as the maximum value of ‘ANS’ and ‘CSUM’ - ‘VAL’.
    - Add ‘CSUM’ to ‘SET’.
Return ‘ANS’.

Solve now