There is a sequence S that consists of n integers, (i.e., a_1, a_2, · · · , a_n). Given the sequence, you can pick any adjacent integers and multiply them to synthesize a new sequence. However, each integer could be multiplied with only one integer. For example, when a sequence is ‘1,1,2,3’, ‘1, 1 × 2, 3’ is a valid synthesized sequence but ‘1 × 1 × 2, 3’ is not. With this multiplication, you need to maximize the sum of a sequence. For example, in case of ‘1, 1, 2, 3’, the answer is ‘1, 1, 2 × 3’.

Give an efficient algorithm to find such a synthesized sequence that maximizes the sum of its elements, starting from a sequence S with n integers, (i.e., a_1 , a_2 , · · · , a_n ).

It seems that dynamic programming is a key idea to solve this exercise, but I could not construct an algorithm depending on the previous step of iteration. Would be happy to know your comments.