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
- 8397 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 |
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
Who ever has red card says truth black card says false 2 guys a and b a says "iam b i have red card " who is he wat card he has thats all from apti i know
In the town called Alibaug, the following facts are true: ? No two inhabitants have exactly the same number of hairs. ? No inhabitants has exactly 2025 hairs. ? There are more inhabitants than there are hairs on the head of any one inhabitants. What is the largest possible number of the inhabitants of Alibaug?
Three friends divided some bullets equally. After all of them shot 4 bullets the total number of bullets remaining is equal to the bullets each had after division. Find the original number divided.
16 Answers Directi, Infosys, L&T, Shreyas, TCS, Turing Software,
Two planes take off at the same exact moment. They are flying across the Atlantic. One leaves New York and is flying to Paris at 500 miles per hour. The other leaves Paris and is flying to New York at only 450 miles per hour ( because of a strong head wind ). Which one will be closer to Paris when they meet?
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?
If A+B=C, D-C=A and E-B=C, then what does D+F stands for? Provide your answer in letter terms as well as in number terms.
iwant to know which type of questions were coming in tcs company
A polygon has 1325 diagonals. How many vertices does it have?
In a city, The police has surrounded the Bank. There are 50 people in the building. Each person is either an engineer or a manager of the bank. All computer files have been deleted, and all documents have been shredded by the managers.
2-3 ques on GDP growth rate ?
A number of 9 digits has the following properties: ? The number comprising the leftmost two digits is divisible by 2, that comprising the leftmost three digits is divisible by 3, the leftmost four by 4, the leftmost five by 5, and so on for the nine digits of the number i.e. the number formed from the first n digits is divisible by n, 2<=n<=9. ? Each digit in the number is different i.e. no digits are repeated. ? The digit 0 does not occur in the number i.e. it is comprised only of the digits 1-9 in some order. Find the number.
10 Answers Citrix, HM Solutions, Wipro,
English 
