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
- 8364 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 |
sir i need catholic syrian bank previous question papers fully. it will be helpful for me to greater extend .please do the needful to me.
there are 6 balls all of same weight except one ball. u r given a weighing balance. in how many trys can u find the ball tat has different weight? (the ball can b heavier or lighter than the rest)
Taurus+pisces =scorpio,substitute the digits for the following letter to make the following addition true?
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?
i want to know tips if any one have any idea about interview at nielsen market research company
You have 13 balls which all look identical. All the balls are the same weight except for one. Using only a balance scale, can find the odd one out with only 3 weighings? Is it possible to always tell if the odd one out is heavier or lighter than the other balls?
if 12+22=24 23+8=6 32+13=40 73+16=144 then 36+2=?
3 blocks are chosen randomly on a chessboard. What is the probability that they are in the same diagonal?
9 9 9 9 5 5 5 5 3 3 3 3 1 1 1 1 is me se kin 6 number ka total 21 hota he..? its challange..
53 Answers Bhel, TCS, TGB,
Find out all possible groups of three different numbers that add up to 13 and arrange them according to given condition. If one number is 9, it must go with 1 and 3. If one number is 8, it must go with either 1 and 4 or 2 and 3. If one number is 7, it must go with either 1 and 5 or 2 and 4. If one number is 6, it must go with either 2 and 5 or 3 and 4.
Implement a multiple-reader-single-writer lock given a compare-and-swap instruction. Readers cannot overtake waiting writers.
Love love it.. friends need it.. relationing start with it.. life ends with it..
English 
