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
- 8277 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 |
pleae send me previous five years SBI clerical questions to my mail(kristy.george@yahoo.com)
0 Answers State Bank Of India SBI,
Submit Answer Users Answer (48) BrainVista Answer Puzzle A Friend Add to Favourite Back to Search Result Hello sajeesh murali ? my Answers ? my Favourites ? Modify Personal Info ? Subscribe ? Logout ? Jigsaw Puzzle ? Join the Dots ? Marbles Game ? Balls Game ? Towers of Hanoi ? Think Number ? Find A Day Brain Teaser No Three Gold (G) coins, three Silver (S) coins and three Copper (C) coins are arranged in a single row as follow: G S C G S C G S C ? Only 2 adjacent unlike coins can be moved at any one time. ? The moved coins must be in contact with at least one other coin in line. i.e. no pair of coins is to be moved and placed away from the remaining ones. ? No coin pairs can be reversed i.e. a S-C combination must remain in that order in its new positionwhen it is moved. What is the minimum number of moves required to get all the coins in following order? C C C S S S G G G Show all moves.
You have 8 marbles. 7 marbles weigh 1 ounce each, & one marble weighs 1.5 ounces. You are unable to determine which is the heavier marble by looking at them. You have a weighing scale that consists of 2 pans, but the scale is only good for 2 total weighings. How can you determine which marble is the heaviest one using the scale & in 2 weighings?
How long would it take you to count 1 billion orally if you could count 200 every minute and were given a day off every four years?
On 20 feet high pol a monkey climb/jump 4 feet and every time he fel/slip down 3 feet then, how many jump/climb he reach at top of the pol?
16 Answers Delhi Police, Ellar Infotech, LIC, Syntel,
A person wanted to withdraw X rupees and Y paise from the bank. But cashier made a mistake and gave him Y rupees and X paise. Neither the person nor the cashier noticed that. After spending 20 paise, the person counts the money. And to his surprise, he has double the amount he wanted to withdraw. Find X and Y.
|3\3 9/9| ! 3["9"" ["39"" | \9/ | ¡ "9""]3 ""9"] YOU "" "" understand this Mssg!! Send
5 Answers Olive Builders, Satyam,
If a monkey climbes 3mts in 1hr and slips back 2mts. What the time taken to climb 20mts .
plz send me aptitude test questions on my email id bpraichur@gmail.com
the age of baby will b 5 time after 20 yrs what is present age?
You have 8 coins. 3 of them weigh x units, 3 y units, 1 a units and 1 b units. They are all mixed and look identical. You have to find the lightest coin in minimum number of weighing (balance)
Karan bought a little box of midget matches, each one inch in length. He found that he could arrange them all in the form of a triangle whose area was just as many square inches as there were matches. He then used up six of the matches, and found that with the remainder he could again construct another triangle whose area was just as many square inches as there were matches. And using another six matches he could again do precisely the same. How many matches were there in the box originally? Note that the match-box can hold maximum of 50 matches.
English 
