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
- 7484 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 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,
wat will be the next number in the series.... 1,3,5,9,12,21,..
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,
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."
Annie, Bunnie, Candy and Dina visited Edy on 14th February. 1. The time of each visit was as follows: - Annie at 8:00 - Bunnie at 9:00 - Candy at 10:00 - Dina at 11:00 Each time mentioned above may be either AM or PM. 2. Candy did not visit Edy between Bunnie and Dina. 3. At least one female visited Edy between Annie and Bunnie. 4. Annie did not visit Edy before both Candy and Dina. Can you tell at what time did they individually visit Edy?
2. At a recent painting competition, jonneys rendition of a constable was not last. priya only just managed to avoid last place and came third. the lady who painted a monkey was very successful and took first place. mary beat the lady who painted the temple and the lady who painted the flower beat sachin. can you determine who painted what and who won?
a pipe fill a tank in 3hrs.another pipe fill that same tank in 2hrs.if both pipe inserted in tank to fill it how timw it will take to fill?
14 Answers Infosys, Zycus Infotech,
plz send me aptitude test questions on my email id bpraichur@gmail.com
Sarika multiplied 414 by certain number and obtained 69958 as the answer. But she found that there is some error in the answer - both the 9s in the answer are wrong and all the other digits are correct. Can you find the correct answer?
There are four friends, one weekend they plan to go to a picnic. Each family have husband and wife with two kids each, further each kid has 2 pets. Total how many went to the picnic?
Mr. Black, Mr. White and Mr. Grey were chatting in the Yahoo conference. They were wearing a black suit, a white suit and a grey suit, not necessarily in the same order. Mr. Grey sent message, "We all are wearing suit that are of the same color as our names but none of us is wearing a suit that is the same color as his name." On that a person wearing the white suit replied, "What difference does that make?" Can you tell what color suit each of the three persons had on?
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.
English 
