Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 1 down vote favorite

I recently participated in a competition where I was asked this question. Given an array with lengths what is the area of the biggest rectangle that can be made using ALL the lengths. The lengths can be added but not broken in between.

Example: [ 4,2,4,4,6,8 ] given this array the best we can do is make a rectangle of sides 8 and 6 like this.

enter image description here

giving an area of 8 * 6 = 48.

I am a beginner and even after a long hard think about how to do it I am unable to get anywhere. I am not looking for a solution but any clue to nudge me in the right direction would be appreciated.

TIA

share|improve this question
2  
I voted to close as off-topic. If you ask a question here, you have to present it as a competition, which can be won by the audience. Your question fits better on StackOverflow. – user unknown Sep 3 '11 at 18:00
btw.: I don't understand the task. What does it mean, the area of biggest rectangle, made from the lengths? What does the diagram show? – user unknown Sep 3 '11 at 18:03
@user unknown It was closed on StackOverflow (off topic), see here. Nevertheless I think you're right. – Howard Sep 3 '11 at 18:04
this was closed of at stack overflow too. stackoverflow.com/questions/7294548/programming-puzzle. thanks anyways, I was new to this site(not an excuse I know!) – John Sep 3 '11 at 18:08
1  
The StackOverflow question is open again now. – Joey Adams Sep 3 '11 at 19:25
show 8 more comments

closed as off topic by user unknown, Peter Taylor, gnibbler♦ Sep 5 '11 at 1:20

Questions on Programming Puzzles & Code Golf Stack Exchange are expected to relate to programming puzzle or code golf within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

2 Answers

up vote 2 down vote

Total of array items will provide maximum perimeter of rectangle. So total is 28. find to maximum a*b we need to use combinations of a+b = 14. the numbers, which are closer to a+b/2 will give you highest multiply value.

1*13 = 13, 2*12 = 24, 3*11 = 33, 4*10 = 40, 5*9 = 45, 6*8 = 48, 7*7 = 49

As you are not able to use 7*7, seems like 6*8 is the best.

share|improve this answer
up vote 0 down vote

Certainly a brute force approach will work. Assign each of your segments to one of the 4 sides of the rectangle (4^n possible assignments), then just check if the result has the same total length on opposite sides, and if so compute the total area and see if it is bigger than any you've found so far.

share|improve this answer
Thank you for the answer. Can I take it that there are no better solutions for this using dynamic or greedy strategies? – John Sep 4 '11 at 6:47
1  
This question has been answered at stackoverflow.com/questions/7294548/… – John Sep 4 '11 at 7:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.