Question: 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 and the relative ordering of elements of A and B in C is not reversed.
eg
A= { 2, 1, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.

Solution: A simple DP problem with the following recurrence
Condition : S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])
If in the above condition, the max is due to A[i]*A[i+1], then the merged array will have A[i] in (i+j)th place and A[i+1] at (i+j+1)th place and i will be i+=2, similarly if max is due to A[i]*B[j], then merged array will have A[i] in (i+j)th place and B[j] in (i+j+1)th place and same for the third one.
i is the index of the elements in A array and j in B array and S[i+j-1] is the max sum upto the current state.
const int Max = 1000;
vector a,b;
int n;

int memo[Max][Max];

int solve(int i,int j) {

if(i == n) {
int ret = 0;
for (int k=j;k ret += b[k] * b[k+1];
++k;
}
return ret;
}
if(j == n) {
int ret = 0;
for (int k = i; k < n; k++) {
ret += a[k] * a[k+1];
++k;
}
return ret;
}

int&ret = memo[i][j];
if(ret != -1) return ret;

ret = -INF;
// Three possibilities.
// (i,i+1) ; (j,j+1) ; [(i,j) == (j,i)]
if(i + 1 < n) {
ret = max(ret, a[i] * a[i+1] + solve(i+2,j));
}
if(j + 1 < n) {
ret = max(ret, b[j] * b[j+1] + solve(i,j+2));
}
ret = max(ret, a[i]*b[j] + solve(i+1,j+1));
return ret;
}
int main() {

scanf("%d",&n);
a.resize(n); b.resize(n);

for (int i=0;i for (int i=0;i
memset(memo, -1, sizeof memo);
printf("%d\n",solve(0,0));
return 0;

}