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
- 8396 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 man got 30 aples in 1 Rs.Now he want 20% of profit on it. How many apples He should Sell in 1 Rs.??
How many possible combinations are there in a 3x3x3 rubics cube? In other words, if you wanted to solve the rubics cube by trying different combinations, how many might it take you (worst case senerio)? How many for a 4x4x4 cube?
One light light flashes 3 times in a minute and an another light flases 3 times in 2 minutes.Find the duration after which both lights will flash same number of times.
100 Gold Coins Five pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all extremely intelligent, treacherous and selfish (especially the captain). The captain always proposes a distribution of the loot. All pirates vote on the proposal, and if half the crew or more go "Aye", the loot is divided as proposed, as no pirate would be willing to take on the captain without superior force on their side. If the captain fails to obtain support of at least half his crew (which includes himself), he faces a mutiny, and all pirates will turn against him and make him walk the plank. The pirates start over again with the next senior pirate as captain. What is the maximum number of coins the captain can keep without risking his life?
what makes a road as abroad?
What is the syllabus for numerical aptitude exam to be held by the United bank of India. Plz inform me through email. Thanking You!
A man has Ten Horses and nine stables as shown here. [] [] [] [] [] [] [] [] [] The man wants to fit Ten Horses into nine stables. How can he fit Ten horses into nine stables?
no.1-6 first is added the last 3 are subtracted , arrange the no. so that each sum and difference give the same answer
3 Answers Karur Vysya Bank KVB,
xx7 and xxx are two numbers and we have to mulitply them xx7 xxx ______ xxxx xxxxxx ______ 3xxx17 find all x's
how many zeros are there at the end of product between 1 to 100
47 Answers Infosys, SIP, TATA, Tech Mahindra, Vodafone,
A cube is divided into 125 pieces.. then four columns are removed then coloured all side black.. i) how many 0 side painted cubes? ii) how many 1 side painted cubes? iii) how many 2 side painted cubes? iV) how many 3 side painted cubes? V) how many 4 side painted cubes?
7 Answers Stairway Engineering, Tata Elxsi,
X is a five letter word.X is a talent in u.if u remove 1st letter X is dead. if u remove 1st 2 letters x is sick.what is X?
English 
