Why Cherry Blossoms Bloomed on Info Island
InterviewTime limit2sMemory limit256 MB
Split a sequence of N numbers into four consecutive nonempty groups, maximizing the sum of the four group products.
- Level
Easy2 of 10
- Topics
- Brute force, Implementation, Array
- Solved
- No attempts yet
Problem
Cherry blossoms have bloomed on Info Island!
Ukje saw the flowers in full bloom on Info Island and had a good idea. He would prepare the four signs below and set them up in the flower garden on Info Island.
In the flower garden on the first floor of Info Island, a total of N cherry trees stand in a row. Each cherry tree has A1, A2, ..., AN cherry blossoms in that order. Ukje divided these cherry trees into exactly four groups and placed a sign to represent each group.
There is a special rule for the division. For four groups [i, j], where the product of the blossom counts in a group is Pi,j = Ai × Ai+1 × ... × Aj-1 × Aj (i ≤ j), he divided them so that the sum of the four P values is maximized. In other words, he multiplied all the blossom counts within each group and divided the trees so that the sum of the four products is maximized. Ukje grouped only consecutive trees into one group, and every tree was included in exactly one group with none left out. Also, each group contained at least one tree.
On your way home after a hard day, you saw the flowers in full bloom and the signs on the first floor of Info Island. And suddenly you became curious about the value of the maximized sum of the four P values.
What is it?
Input
The first line gives the number of cherry trees N. (4 ≤ N ≤ 10)
The second line gives the number of cherry blossoms Ai on each of the N trees, in order. (1 ≤ Ai ≤ 5)
Output
What is it?