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
- 7482 Views
- Infosys, TCS, I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
4 cards are placed on a table, each card has two colors. U don't know the color of the back side of eachcard.4 persons A B C and D are sitting on the table before the cards. They can see Red, Green Red and blue.Out of the 4 poeple 2 always lie. They see the color on the reverse side and give the following comment A: Yello/green B: Neither Blue/nor Green c: Blue/Yello D: Blue/ Yello find out the color on the other side of the 4 cards. No. of animals is 11 more than the no. of birds. If the no. of birds were the no. of animals and no. of animals were the no. of birds( ie., interchanging no.s of animals and birds.), the total no. of legs get reduced by one fifth (1/5). How many no. of birds and animals were there?
Ship is 180 miles away from shore. At that time a plane started from shore to pass some information to the ship with 10 times velocity of ship's velocity. At what distance from shore they will meat?
What is the syllabus for numerical aptitude exam to be held by the United bank of India. Plz inform me through email. Thanking You!
why should we hire the others waiting to be interviewed?
what three specific job positions do you target from qatar airways group u.k?
plz send me aptitude test questions on my email id bpraichur@gmail.com
what job position/s are you currently holding with your current employer?
Three neighbours are there. 1st one lends 2nd and 3rd that many no.of tractors that then already each had.After few months , 2nd lends to 1st and 3rd that many tractors then they had. After a few months 3rd lends to 1st and 2nd that many tractors then they had.Now each of them got 24. Find howmany they had initially?
In a soap company a soap is manufactured with 11 parts. For making one soap you will get 1 part as crap. At the end of the day u have 251 such scraps. From that how many soaps can be manufactured?
foot is related to man in the same way hoof is related to...........
how soon can you travel down to start your new job?
P pages read in d mins after day p+1 pages read in d+1 mins last day 379 pages done in 317 mins find p+4
In rail road there are some stations. Each station should have tickets to all other stations.If they add some new stations they need 46 more tickets.How many stations are there before and after adding the stations?
In country X, democratic, conservative and justice parties have fought three civil wars in twenty years. TO restore stability an agreement is reached to rotate the top offices President, Prime Minister and Army Chief among the parties so that each party controls one and only one office at all times. The three top office holders must each have two deputies, one from each of the other parties. Each deputy must choose a staff composed of equally members of his or her chiefs party and member of the third party. 1. When Justice party holds one of the top offices, which of the following cannot be true (a) Some of the staff members within that office are justice party members (b) Some of the staff members within that office are democratic party members (c) Two of the deputies within the other offices are justice party members (d) Two of the deputies within the other offices are conservative party members (e) Some of the staff members within the other offices are justice party members. 2. When the democratic party holds presidency, the staff of the prime minister's deputies are composed I. One-fourth of democratic party members II. One-half of justice party members and one-fourth of conservative party members III. One-half of conservative party members and one-fourth of justice party members. (a) I only (b) I and II only (c) II or III but not both (d) I and II or I and III (e) None of these 3. Which of the following is allowable under the rules as stated: (a) More than half of the staff within a given office belonging to a single party (b) Half of the staff within a given office belonging to a single party (c) Any person having a member of the same party as his or her immediate superior (d) Half the total number of staff members in all three offices belonging to a single party (e) Half the staff members in a given office belonging to parties different from the party of the top office holder in that office. 4. The office of the Army Chief passes from Conservative to Justice party. Which of the following must be fired. (a) The democratic deputy and all staff members belonging to Justice party (b) Justice party deputy and all his or hers staff members (c) Justice party deputy and half of his Conservative staff members in the chief of staff office (d) The Conservative deputy and all of his or her staff members belonging to Conservative party (e) No deputies and all staff members belonging to conservative parties.
Three members are hunting in a forest.While crossing a streem cartridges of two of them gets wetted up.Then the third person decides his cartidges equally. After 4 shots of each person, total cartridges remaining are equal to what each had initially after sharing.How many total cartridges they initially they shared?
