Synthesized sequence

help
1

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.

2

just sort the array and multiply the last two digits.

3

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

4

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?

5

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

6

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);