稳定地合并两个数组以最大化相邻元素的乘积
下面是一个面试问题，我无法用低于指数复杂度的复杂度来回答。虽然这似乎是一个DP问题，但我无法形成基本情况并进行适当的分析。任何帮助都是非常感谢的。
给你两个数组，每个数组的大小是'n‘。您需要稳定地合并这些数组，以便在新的数组中，连续元素的乘积和最大化。
例如的
A= { 2，1，5}
B= { 3，7，9}
稳定地合并A= {a1，a2，a3}和B= {b1，b2，b3}将创建一个具有2*n个元素的数组C。例如，通过合并(稳定)A和B，假设C={ b1，a1，a2，a3，b2，b3 }，那么sum = b1*a1 + a2*a3 + b2*b3应该是最大值。
回答 7
Stack Overflow用户
发布于 2012-08-05 09:37:08
让我们将ci，j定义为相同问题的解决方案，但数组从i开始到左侧结束。和j在右端结束。因此，c0,0将给出原始问题的解决方案。
ci，j由。
- MaxValue =最大值。
- NeedsPairing = true或false =取决于最左边的元素是不成对的。
- 子键= p、q或NULL =定义子关键字，最终达到此级别的最优和。
现在定义此DP的最佳子结构
c[i,j] = if(NeedsPairing) { left[i]*right[j] } + Max { c[i+1, j], c[i, j+1] }在这段代码中捕获了更详细的信息。
if (lstart == lend)
{
if (rstart == rend)
{
nodeResult = new NodeData() { Max = 0, Child = null, NeedsPairing = false };
}
else
{
nodeResult = new NodeData()
{
Max = ComputeMax(right, rstart),
NeedsPairing = (rend - rstart) % 2 != 0,
Child = null
};
}
}
else
{
if (rstart == rend)
{
nodeResult = new NodeData()
{
Max = ComputeMax(left, lstart),
NeedsPairing = (lend - lstart) % 2 != 0,
Child = null
};
}
else
{
var downLef = Solve(left, lstart + 1, right, rstart);
var lefResNode = new NodeData()
{
Child = Tuple.Create(lstart + 1, rstart),
};
if (downLef.NeedsPairing)
{
lefResNode.Max = downLef.Max + left[lstart] * right[rstart];
lefResNode.NeedsPairing = false;
}
else
{
lefResNode.Max = downLef.Max;
lefResNode.NeedsPairing = true;
}
var downRt = Solve(left, lstart, right, rstart + 1);
var rtResNode = new NodeData()
{
Child = Tuple.Create(lstart, rstart + 1),
};
if (downRt.NeedsPairing)
{
rtResNode.Max = downRt.Max + right[rstart] * left[lstart];
rtResNode.NeedsPairing = false;
}
else
{
rtResNode.Max = downRt.Max;
rtResNode.NeedsPairing = true;
}
if (lefResNode.Max > rtResNode.Max)
{
nodeResult = lefResNode;
}
else
{
nodeResult = rtResNode;
}
}
}我们使用记忆法来防止再次解决子问题。
Dictionary<Tuple<int, int>, NodeData> memoization = new Dictionary<Tuple<int, int>, NodeData>();最后，我们使用NodeData.Child回溯路径。
Stack Overflow用户
发布于 2012-07-27 15:38:04
对于A= {a1，a2，...，an}，B= {b1，b2，...，bn}，
定义DPi，j为{ai，...，an}和{bj，...，bn}之间的最大稳定合并和。
(1 <= i <= n+1，1 <= j <= n+1)
DPn+1，n+1 = 0，DPn+1，k= bk*bk+1 +...+ bn-1*bn，DPk，n+1 = ak*ak+1 +...+ an-1*an。
DPn，k= max{an*bk + bk+1*bk+2 +..+ bn-1*bn，DPn，k+2 + bk*bk+1}
DPk，n= max{ak*bn + ak+1*ak+2 +..+ an-1*an，DPk+2，n+ ak*ak+1}
DPi，j= max{DPi+2，j+ ai*ai+1，DPi，j+2 + bi*bi+1，DPi+1，j+1 + ai*bi}。
然后返回DP1,1。
说明:在每一步中，你必须考虑3个选项:从剩余A中获取前2个元素，从剩余B中获取前2个元素，或者从A和B中同时获取两个元素(因为你不能改变A和B的顺序，所以必须从A中获取第一个元素，从B中获取第一个元素)。
Stack Overflow用户
发布于 2012-07-29 20:41:44
我的解决方案很简单。我只是探索所有可能的稳定合并。遵循正在运行的C++程序：
#include<iostream>
using namespace std;
void find_max_sum(int *arr1, int len1, int *arr2, int len2, int sum, int& max_sum){
if(len1 >= 2)
find_max_sum(arr1+2, len1-2, arr2, len2, sum+(arr1[0]*arr1[1]), max_sum);
if(len1 >= 1 && len2 >= 1)
find_max_sum(arr1+1, len1-1, arr2+1, len2-1, sum+(arr1[0]*arr2[0]), max_sum);
if(len2 >= 2)
find_max_sum(arr1, len1, arr2+2, len2-2, sum+(arr2[0]*arr2[1]), max_sum);
if(len1 == 0 && len2 == 0 && sum > max_sum)
max_sum = sum;
}
int main(){
int arr1[3] = {2,1,3};
int arr2[3] = {3,7,9};
int max_sum=0;
find_max_sum(arr1, 3, arr2, 3, 0, max_sum);
cout<<max_sum<<endl;
return 0;
}https://stackoverflow.com/questions/11682472
复制相似问题