Interested to Buy Any Domain ? << Click Here >> for more details...
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
- 8470 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 |
Find the smallest number such that if its rightmost digit is placed at its left end, the new number so formed is precisely 50% larger than the original number.
Montu, Bantu, Chantu and Pintu have pets. Montu says, "If Pintu and I each have a dog, then exactly one of Bantu and Chantu has a dog." Bantu says, "If Chantu and I each have a cat, then exactly one of Montu and Pintu has a dog." Chantu says, "If Montu and I each have a dog, then exactly one of Bantu and Pintu has a cat." Pintu says, "If Bantu and I each have a cat, then exactly one of Bantu and I has a dog." Only one of the four is telling the truth. Who is telling the truth?
A husband and wife have a combined age of 91. The husband is now twice as old as his wife was when he was as old as she is now. How old is wife?
what is the name of our prime minister before the death of indira gandhi???????????
22 Answers BPO, HCL,
In a certain game, if 2 wixsomes are worth 3 changs, and 4 changs are worth 1 plut, then 6 plutes are worth how many wixsomes?
2. At a recent painting competition, jonneys rendition of a constable was not last. priya only just managed to avoid last place and came third. the lady who painted a monkey was very successful and took first place. mary beat the lady who painted the temple and the lady who painted the flower beat sachin. can you determine who painted what and who won?
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?
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?
Three friends divided some bullets equally. After all of them shot 4 bullets the total number of bullets remaining is equal to the bullets each had after division. Find the original number divided.
16 Answers Directi, Infosys, L&T, Shreyas, TCS, Turing Software,
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,
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
Veeru says to Jay, "Can you figure out how many Eggs I have in my bucket?" He gives 3 clues to Jay: If the number of Eggs I have 1. is a multiple of 5, it is a number between 1 and 19 2. is not a multiple of 8, it is a number between 20 and 29 3. is not a multiple of 10, it is a number between 30 and 39 How many Eggs does Veeru have in his bucket?
English 
