|There is an empty grass field with an infinitely long straight wall. You are going to create a rectangular garden against the wall. Three sides of the garden will be enclosed with a fence. The fourth side of the garden is formed by part of the wall.
You currently have some fence segments. Each side of your fence can be created by connecting some of these segments. The length of a side of the fence is equal to the sum of the lengths of the fence segments that form it. The length of each side of the fence must be exactly equal to the length of the corresponding side of the rectangular garden. As in real life, each fence segment may only be used at most once.
Fortunately, you have a saw that can cut at most one of these segments into two shorter segments. The saw will break after being used one time. You may cut the one segment into two shorter segments at any point between its endpoints (non-integer length is allowed). Note that the total length of the two shorter segments created must be equal to the length of the original segment.
You are given int segment. The i-th element of segment represents the length of the i-th fence segment. Using these segments construct the garden fence (as described above) enclosing the maximum area possible and return the length of the garden's side parallel to the wall. If the maximum area can be formed in more than one way then return the largest parallel-to-the-wall length that gives the maximum area.
|-||segment will contain between 2 and 40 elements, inclusive.|
|-||Each element of segment will be between 1 and 100,000,000, inclusive.|