# Construct the largest possible rectangle out of line segments of given lengths [closed]

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.

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

-
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
The StackOverflow question is open again now. – Joey Adams Sep 3 '11 at 19:25

## 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.

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.

-

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.

-
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
This question has been answered at stackoverflow.com/questions/7294548/… – John Sep 4 '11 at 7:52