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
- 8362 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 |
A person is standing at the top of a 100mt building, he has a rope 75mts long and the only way he can come down is through the rope. He can cut the rope also he can tie the rope at any point on the building, but he cant jump and ofcourse dont even think about the stairs :D Find out the best way he'll come down.
14 Answers Compro, Huawei, Oracle, Tech Mahindra,
Ship is 180 miles away from shore. At that time a plane started from shore to pass some information to the ship with 10 times velocity of ship's velocity. At what distance from shore they will meat?
If you started a business in which you earned Rs.1 on the first day, Rs.3 on the second day, Rs.5 on the third day, Rs.7 on the fourth day, & so on. How much would you have earned with this business after 50 years (assuming there are exactly 365 days in every year)?
100 Gold Coins Five pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all extremely intelligent, treacherous and selfish (especially the captain). The captain always proposes a distribution of the loot. All pirates vote on the proposal, and if half the crew or more go "Aye", the loot is divided as proposed, as no pirate would be willing to take on the captain without superior force on their side. If the captain fails to obtain support of at least half his crew (which includes himself), he faces a mutiny, and all pirates will turn against him and make him walk the plank. The pirates start over again with the next senior pirate as captain. What is the maximum number of coins the captain can keep without risking his life?
If a monkey climbs 3 mts and then slips back 2 mts in alternate hour , how much time he will take to climbs 20 mts?
if you are running in the race and you overtakes 2nd no player then whats your position?
A cube is made of a white material, but the exterior is painted black. If the cube is cut into 125 smaller cubes of exactly the same size, how many of the cubes will have atleast 2 of their sides painted black?
Plz mail me some aptitute questions which helps me to face SBI clerical exam.
3 Answers Genpact, State Bank Of India SBI,
xx7 and xxx are two numbers and we have to mulitply them xx7 xxx ______ xxxx xxxxxx ______ 3xxx17 find all x's
A farmer needs 8 gallons of water. He has only three unmared buckets, two 6 gallon and one 11 gallon bucket. How can he collect 8 gallons of water using three unmarked buckets? Provide solution with minimal water wastage.
how would u find d exact number of white maruti cars in mumbai???
15 Answers Bhel, Infosys, RR, TCS,
We have 2 poles 5 m and 7 m height ropes are connected from top of one to tthe bottem of another find the intersection height of those poles.
English 
