The following is an interview question which I am unable to answer in a complexity less than an exponential complexity. Though it seems to be an DP problem, I am unable to form the base cases and analyze it properly. Any help is appreciated.
You are given 2 arrays of size 'n' each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized.
For example
A= { 2, 1, 5}
B= { 3, 7, 9}
Stable merging A = {a1, a2, a3} and B = {b1, b2, b3} will create an array C with 2*n elements. For example, say C = { b1, a1, a2, a3, b2, b3 } by merging (stable) A and B. Then the sum = b1*a1 + a2*a3 + b2*b3 should be a maximum.