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
- 7838 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 |
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.
if 1+1 = 2 what will be 1-1 ? if 1+1 = 11 what will be 1-1 ? if 1+1 = 1 what will be 1-1 ?
How many ways are there of arranging the sixteen black or white pieces of a standard international chess set on the first two rows of the board? Given that each pawn is identical and each rook, knight and bishop is identical to its pair.
There are 3 colored boxes - Red, Green and Blue. Each box contains 2 envelopes. Each envelope contains money - two of them contain Rs. 25000 each, two of them contain Rs. 15000 each and remaining two contain Rs. 10000 each. There is one statement written on the cover of each box. * Red Box: Both, a red box and a blue box contain Rs. 10000 each. * Green Box: Both, a green box and a red box contain Rs. 25000 each. * Blue Box: Both, a blue box and a green box contain Rs. 15000 each. Only one of the above 3 statements is true and the corresponding box contains the maximum amount. Can you tell which box contains the maximum amount and how much?
one boys usually takes some flowers to temple. three temples are there.each temple has the pool infront of it.the pool's speciality is when we put one thing it doubles that. the boy took all the flowers and put it into the pool. then he took some flowers and submit it in the first temple.then he put the remaining flowers in the second pool and it gets doubles then the took some of them & put them in the second temple. he put the remaining flowers in the third pool and submit all the flowers in that temple.THE CONDITION IS the flowers submited in the temple are equal in number. How much flowers the boy took initially?? How many flowers he submit in each temple??
Ali Baba had four sons, to whom he bequeathed his 39 camels, with the proviso that the legacy be divided in the following way : The oldest son was to receive one half the property, the next a quarter, the third an eighth and the youngest one tenth. The four brothers were at a loss as how to divide the inheritance among themselves without cutting up a camel, until a stranger appeared upon the scene. Dismounting from his camel, he asked if he might help, for he knew just what to do. The brothers gratefully accepted his offer. Adding his own camel to Ali Baba's 39, he divided the 40 as per the will. The oldest son received 20, the next 10, the third 5 and the youngest 4. One camel remained : this was his, which he mounted and rode away. Scratching their heads in amazement, they started calculating. The oldest thought : is not 20 greater than the half of 39? Someone must have received less than his proper share ! But each brother discovered that he had received more than his due. How is it possible?
A tank can be filled by pipe A in 30 minutes and by pipe B in 24 minutes. Outlet pipe C can empty the full tank in X minutes. If the tank is empty initially and if all the three pipes A, B and C are opened simultaneously, the tank will NEVER be full. Give the maximal possible value of X.
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
Jim lies a lot. He tells the truth on only one day in a week. One day he said: "I lie on Mondays and Tuesdays." The next day he said: "Today is either Sunday, Saturday or Thursday." The next day he said: "I lie on Fridays and Wednesdays." On which day of the week does Jim tell the truth?
what do mean welder
Raj has a jewel chest containing Rings, Pins and Ear-rings. The chest contains 26 pieces. Raj has 2 1/2 times as many rings as pins, and the number of pairs of earrings is 4 less than the number of rings. How many earrings does Raj have?
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?
English 
