# Synthesized sequence

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.

just sort the array and multiply the last two digits.

It is required to find an efficient algorithm, sorting will take (nlogn) time and as an example, your approach is not correct: take <1,3,2,1> and you will find its synthesized sequenceis <1, 3*2, 1>.

You are not supposed to sort the array.

So, you are not supposed to alter the sequence. Hence, sorting would not help.
I guess, you can compare the values (a_i + a_{i+1}) vs (a_i\times a_{i+1}) and solve it appropriately. ( I am not sure)
@carre, could you kindly help?

you can define a dp state as dp[element][used], where element goes from 1 to n and used is 0 or 1 and corresponds to the case you have used the current element in a multiplication with previous one or not

sorry i thought we could change the sequence.
I tried it and i got to this algorithm,

int check=0;
for(int i=0;i<n-2;i++)
{
if(check< max(arr[i]*arr[i+1] , arr[i +1]*arr[i+2] ) )
check=max;
}
so you can get your ans in O(n);