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
- 7480 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 |
do you have reference list?
I'm 11 letters word & a famous place in India,letters 6,7,8,9,10,11 is a fruitand 6,7,5,3 a part of face,6238 a geometrical shape.783 a bird.find me
11 Answers ACC, Raisoni, Tech Mahindra,
one hen and its three kids where cross the road and one kid said we all seven cross road sucessfully,how seven?
In rail road there are some stations. Each station should have tickets to all other stations.If they add some new stations they need 46 more tickets.How many stations are there before and after adding the stations?
A man was looking at a portrait. Someone asked him, "Whose picture are you looking at?" He replied, pointing at the portrait: "Brothers and sisters have I none, but this man's son is my father's son." Now whose picture is the man looking at?
Reshma is standing in front of her room.Ramu is coming from north towdars her and he can see his shadow falling on his right.In which direction she is standing?
12 members were present at a board meeting. Each member shook hands with all of the other members before & after the meeting. How many hand shakes were there?
A cube painted on all six sides by red color is divided into 125 equal cubes find i) number of cubes having a)3 faces colored b)2 faces colored c) 1 face colored d)0 faces colored ii)Find probability of picking a cube having red face
1,5,7,40,15,_? next no no arithmetic simple logic...
3 Answers Bosch, iStepup Services, Suzuki,
IDear sir, I have had a data containing of 4 numbers on daily basis for which I would like to know what is the next comming 4 numbers. Based on that data I would like to find out the next comming numbers. Support needed. regards chandramohan gudivada 09849974512 cm116_99@yahoo.com Example : 4513, 4132, 1465, 2941, 1762, 1432, 3412, 5283, 7261, 2643, 4751, 2581, 6513 .... and what is the next number in the sequence?
In a city, The police has surrounded the Bank. There are 50 people in the building. Each person is either an engineer or a manager of the bank. All computer files have been deleted, and all documents have been shredded by the managers.
Given the following facts: 1. Dinesh is younger than Farukh and older than Gurmit. 2. Jatin is younger than Chandu and older than Eshrat. 3. Amit is younger than Irfan and older than Chandu. 4. Farukh is younger than Bhavin and older than Hemant. 5. Irfan is younger than Gurmit and older than Jatin. 6. Hemant is older than Gurmit. Who is the Youngest?
English 
