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
- 7470 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 |
what makes a road as abroad?
An anthropologist discovers an isolated tribe whose written alphabet contains only six letters (call the letters A, B, C, D, E and F). The tribe has a taboo against using the same letter twice in the same word. It's never done. If each different sequence of letters constitues a different word in the language, what is the maximum number of six-letter words that the language can employ?
Without using any loops print {{{}}} (u cant use goto,for,while etc..).
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)
Four persons A, B, C and D are playing cards.Each person has one card, laid down on the table below him, which has two different colours on either side. The colours visible on the table are Red, Green, Red and Blue. They see the color on the reverse side and give the following
4 Answers HP, Infosys, TCS, Wipro,
I can take a bca student instead of you then why should i hire you
Find a number which ends with digit 2 such that when you cut this last digit and paste it in the front of the number, the new number value is double that of original.
During a recent school reunion,four men were discussing their starting salaries back in 1962.The salaries in question were 8,10,12 and 14 thousand pounds per year.of course the MP earned the most.Alan earned more thean brain and the doctor earnd more than Derek,the vet.charles could not remember what he started on.Brain,the lawyer,didnot start on 10,000pounds nor did Derek.can you determine who has which job and their starting salaries?
with heavy raining ,At Midnight 12, aap car lekar ja rahe ho aur bus stand par 3 log (80 years woman , ur best friend , ur lover ) khade he....lekin aap kisi ek ko hi apni car me bitha sakte ho..to aap kya karoge aur kyu ????
can you work well under deadlines or pressure?
1 Answers Academy Of Aerospace Aviation, Qatar Airlines,
How will you differentiate a 5 rupee(indian currency)or any five currency coin?Answer me how will you differentiate????? This question is asked in a college appitute test.Any one know help me plzzzzz!!!!!!!!!!!!!
There are 3 persons X, Y and Z. On some day, X lent tractors to Y and Z as many as they had. After a month Y gave as many tractors to X and Z as many as they have. After a month Z did the same thing. At the end of this transaction each one of them had 24. Find the tractors each originally had?
English 
