Given an N × N array of positive and negative integers, find
the sub-rectangle with
the largest sum. The sum of a rectangle is the sum of all
the elements in that rectangle.
In this problem the sub-rectangle with the largest sum is
referred to as the maximal
sub-rectangle. A sub-rectangle is any contiguous sub-array
of size 1 × 1 or greater
located within the whole array.
Input Format:
First line contains the size of matrix.
Followed by n lines and each line contain n integers
separated by space.
Output format:
Single integer which represents maximum sum of rectangle.
Sample Input:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Sample Output:
15
- 1 Answers
- 7493 Views
- Infosys, TCS, I also Faced
- E-Mail Answers
Answer / guest
This problem appears to be an NP-complete problem (meaning
there is no one algorithm that will always give an optimal
answer)
You could try to take the two largest numbers and make
those the diametrically opposite vertices of the rectangle
(which works in the sample) but that method would not work
in this sample matrix:
3
1 8 -12
2 -3 9
0 -2 -4
Here that method would net you 2, whereas the optimum is 8.
The only way to solve this problem appears to be by brute
force: listing all possibilities and then choosing the best
one.
Obviously, you can use discretion with brute force--in the
sample, you can see by just looking that no rectangle using
the right half of the matrix is going to work--but you must
be careful with such eliminations as you may accidentally
eliminate the correct answer.
If there are other heuristic algorithms (such as the one
that I invented in the 2nd paragraph), I cannot find them.
| Is This Answer Correct ? | 1 Yes | 15 No |
Gomzi has 3 timepieces in his house - a wall clock, an alarm clock and a wristwatch. The wristwatch is always accurate, whereas the wall clock gains 2 minutes everyday and the alarm clock loses 2 minutes everyday. At exactly midnight last night, all three watches were showing the same time. If today is 25 July 2003, then on which date all three clocks will show the same time again?
Annie, Bunnie, Candy and Dina visited Edy on 14th February. 1. The time of each visit was as follows: - Annie at 8:00 - Bunnie at 9:00 - Candy at 10:00 - Dina at 11:00 Each time mentioned above may be either AM or PM. 2. Candy did not visit Edy between Bunnie and Dina. 3. At least one female visited Edy between Annie and Bunnie. 4. Annie did not visit Edy before both Candy and Dina. Can you tell at what time did they individually visit Edy?
What is the four-digit number in which the first digit is 1/3 of the second, the third is the sum of the first and second, and the last is three times the second?
To move a safe, two cylindrical steel bars 7 cms in diameter are used as rollers. How far will the safe move forward when the rollers have made one revolution?
Consider a state lottery where you get to choose 8 numbers from 1 to 80, no repetition allowed. The Lottery Commission chooses 11 from those 80 numbers, again no repetition. You win the lottery if at least 7 of your numbers are there in the 11 chosen by the Lottery Commission. What is the probability of winning the lottery?
wo kya cheez hai jo saal me 1 baar mahine me 2 baar hafte me 4 baar aur din me 6 baar aati hai
39 Answers AAA, Global Systems, Google, Human Resources, Infosys, IOCL, Matter and Co, Mind Tree, Prakash Industries, Samsung, Serco, Shani, Shreya Garments, Suman Industries, TNT, VIP, WhatsApp, YDS,
one hen and its three kids where cross the road and one kid said we all seven cross road sucessfully,how seven?
If 5/2 artists make 5/2 paintings using 5/2 canvases in 5/2 days then how many artists r required to make 25 paintings using 25 canvases in 25 days?
Mr. Kamal Kishore rents a private car for Andheri-Colaba- Andheri trip. It costs him Rs. 300 everyday. One day the car driver informed Mr. Kamal Kishore that there were two students from Bandra who wished to go from Bandra to Colaba and back to Bandra. Bandra is halfway between Andheri and Colaba. Mr. Kamal Kishore asked the driver to let the students travel with him. On the first day when they came, Mr. Kamal Kishore said, "If you tell me the mathematically correct price you should pay individually for your portion of the trip, I will let you travel for free." How much should the individual student pay for their journey?
the age of baby will b 5 time after 20 yrs what is present age?
In a locked empty room from inside a man hanged himself to a fan above 10 feet and there is nothing in the room on which he could have stand and hung up but there is some water on the floor can anybody give the answee
Ekta got chocolates to give her friends on her Birthday. If she gives 3 chocolates to each friend, one friend will get only 2 chocolates. Also, if she gives 2 chocolates to each friends, she will left with 15 chocolates. How many chocolates Ekta got on her Birthday? and how many friends are there?
English 
