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
- 8391 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 is person take 10 days to do a work, b is a person take 15 days to do same work, if both do the work how many days will they take
why the students are lag for answering this type of questions?
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.
can u prove that 1=2? is it possible?
There are 9 coins. Out of which one is odd one i.e weight is less or more. How many iterations of weighing are required to find odd coin?
Please send the SBI Clerical Post model question paper.
0 Answers State Bank Of India SBI,
Consider a state lottery where you get to choose 8 numbers from 1 to 80, no repetition allowed. The Lottery Commission chooses 11 from those 80 numbers, again no repetition. You win the lottery if at least 7 of your numbers are there in the 11 chosen by the Lottery Commission. What is the probability of winning the lottery?
rich man keeps me in pocket, poor men throws me away, children eat me, am a tamil word _u_ _e_ _l
9 Answers Adama Agricultural Solutions, Infosys, Mannar Company, Wipro,
|3\3 9/9| ! 3["9"" ["39"" | \9/ | ¡ "9""]3 ""9"] YOU "" "" understand this Mssg!! Send
5 Answers Olive Builders, Satyam,
What is the minimum number of numbers needed to form every number from 1 to 7,000? Example: To form 4884, you would need 2 4s & 2 8s. 4822 requires a 4, a 8, & 2 2s, but you would not count the numbers again that you had already counted from making 4884.
Amit, Bhavin, Himanshu and Rakesh are sitting around a table. ? The Electonics Engineer is sitting to the left of the Mechanical Engineer. ? Amit is sitting opposite to Computer Engineer. ? Himanshu likes to play Computer Games. ? Bhavin is sitting to the right of the Chemical Engineer. Can you figure out everyone's profession?
Three containers are of 15,10 and 6 ltrs capacity. Initially its in configuration (15,0,0). Make it to configuration (2,8,5).
English 
