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
- 8387 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 |
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?
greatest achievement in life
What is the area of the triangle ABC with A(e,p) B(2e,3p) and C(3e,5p)? where p = PI (3.141592654)
what three specific job positions do you target from qatar airways group u.k?
A soldier looses his way in a thick jungle. At random he walks from his camp but mathematically in an interesting fashion. First he walks one mile East then half mile to North. Then 1/4 mile to West, then 1/8 mile to South and so on making a loop. Finally how far he is from his camp and in which direction?
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.
A lady has fine gloves and hats in her closet- 18 blue, 32 red, and 25 yellow. The lights are out and it is totally dark. In spite of the darkness, she can make out the difference between a hat and a glove. She takes out an item out of the closet only if she is sure that if it is a glove. How many gloves must she take out to make sure she has a pair of each color?
There were two men standing on a street. The one says to the other, "I have 3 daughters, the product of their ages is 36. What is the age of the OLDEST daughter?" The second guy says, "I need more information." So, the first guy says, "The sum of their ages is equal to the address of the house across the street." The second guy looks at the address and says, "I still need more information." So, the first guy says, "My oldest daughter wears a red dress."
RAW means
What is the ten letter city 7 8 9 is a famous festival 3 4 5 is a degree 2 1 is a abbreviation of group of countries 7 6 gives the meaning?
3 boys go to the restaurant. Their bill was 75 rs.. So they contributed 25 each. Manager then gives 5 rs back to the waiter and then waiter gave 3 rs back to them and put 2 rs into his pocket.. So their actual contribution is 24 because they got 1-1 rs back. so 24*3=72 and 2 rs into the waiter's pocket. so 74+2=74 where is 1 rs?
55 Answers College School Exams Tests, Garrison, Google, HCL, Jabong, Merlion, Rainbow Civil Engineers, Renault, TATA, Watair, Wipro,
Somebody marked the six faces of a die with the numbers 1, 2 and 3 - each number twice. The die was put on a table. Four people - Abu, Babu, Calu and Dabu - sat around the table so that each one was able to see only three sides of the die at a glance. ? Abu sees the number 1 and two even numbers. ? Babu and Calu can see three different numbers each. ? Dabu sees number 2 twice and he can't remember the third number. What number is face down on the table?
English 
