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
- 8471 Views
- Infosys, TCS, I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
how soon can you travel down to start your new job?
At 6o'clock ,a watch strokes 6 times.The time between first and last is 30secs.At midnight 12o' clock how much time for all strokes?
P pages read in d mins after day p+1 pages read in d+1 mins last day 379 pages done in 317 mins find p+4
4_4_4_4=22 use all sign of maths
In rail road there are some stations. Each station should have tickets to all other stations.If they add some new stations they need 46 more tickets.How many stations are there before and after adding the stations?
IDear sir, I have had a data containing of 4 numbers on daily basis for which I would like to know what is the next comming 4 numbers. Based on that data I would like to find out the next comming numbers. Support needed. regards chandramohan gudivada 09849974512 cm116_99@yahoo.com Example : 4513, 4132, 1465, 2941, 1762, 1432, 3412, 5283, 7261, 2643, 4751, 2581, 6513 .... and what is the next number in the sequence?
foot is related to man in the same way hoof is related to...........
Three neighbours are there. 1st one lends 2nd and 3rd that many no.of tractors that then already each had.After few months , 2nd lends to 1st and 3rd that many tractors then they had. After a few months 3rd lends to 1st and 2nd that many tractors then they had.Now each of them got 24. Find howmany they had initially?
sir i need generalKnowledge previous questions for rrb secunderabad goods guard exam
Three members are hunting in a forest.While crossing a streem cartridges of two of them gets wetted up.Then the third person decides his cartidges equally. After 4 shots of each person, total cartridges remaining are equal to what each had initially after sharing.How many total cartridges they initially they shared?
what three specific job positions do you target from qatar airways group u.k?
plz send me aptitude test questions on my email id bpraichur@gmail.com
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 is puzzle with the word "CONSTANTINE" and exactly don't know the question if anybody knows the Q&A plz send it ahmed.basha.munna@gmail.com
why should we hire the others waiting to be interviewed?
