以下是一个面试问题，我无法以复杂性而非指数复杂性来回答这个问题。虽然它似乎是一个DP问题，但我无法形成基本案例并对其进行适当分析。任何帮助表示赞赏。
您将获得2个大小为'n'的数组。您需要稳定合并这些数组，以便在新数组中连续元素的乘积和最大化。
例如
A = {2,1,3}
B = {3,7,9}
在稳定合并A和B将给出一个带有'2n'元素的数组C，比如C = {c1，c2，c3，c4，c5，c6}你需要通过合并（稳定）A和B找到一个新的数组C，这样sum = c1 * c2 + c3 * c4 + c5 * c6 ...... n是最大值。
让我们将c [i，j]定义为相同问题的解决方案但是数组从i开始到左边结束。并且j结束为正确。因此c [0,0]将解决原始问题。
c [i，j]由。
现在定义此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;
}
}
}
我们使用memoization来防止再次解决子问题。
Dictionary<Tuple<int, int>, NodeData> memoization = new Dictionary<Tuple<int, int>, NodeData>();
最后我们使用NodeData.Child追溯路径。
对于A = {a1，a2，...，an}，B = {b1，b2，...，bn}，
将DP [i，j]定义为{ai，...，an}和{bj，...，bn}之间的最大稳定合并和。
（1 <= i <= n + 1,1 <= j <= n + 1）
DP [n + 1，n + 1] = 0，DP [n + 1，k] = bk * bk + 1 + ... + bn-1 * bn，DP [k，n + 1] =和*和+1 + ... + on-1 *。
DP [n，k] = max {an * bk + bk + 1 * bk + 2 + .. + bn-1 * bn，DP [n，k + 2] + bk * bk + 1}
DP [k，n] = max {和* bn +和+ 1 *和+ 2 + .. + in-1 *，DP [k + 2，n] +和*和+ 1}
DP [i，j] = max {DP [i + 2，j] + ai * ai + 1，DP [i，j + 2] + bi * bi + 1，DP [i + 1，j + 1] + ai * bi}。
你返回DP [1,1]。
说明：在每个步骤中你必须考虑3个选项：从剩余的A中取出前2个元素，从剩余的B中取出前2个元素，或从A和B中取两个元素（因为你不能改变A和B的顺序，你必须从A中取第一个，从B中取第一个。
我的解决方案很简单。我只是探索所有可能稳定的合并。遵循工作的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;
}
将F(i, j)定义为可通过稳定合并Ai...An和Bj...Bn实现的最大成对和。
在合并的每个步骤中，我们可以选择以下三个选项之一：
A的前两个元素。A的第一个剩余元素和B的第一个剩余元素。B的前两个元素。因此，F(i, j)可以递归定义为：
F(n, n) = 0
F(i, j) = max
(
AiAi+1 + F(i+2, j), //Option 1
AiBj + F(i+1, j+1), //Option 2
BjBj+1 + F(i, j+2) //Option 3
)
为了找到两个列表的最佳合并，我们需要找到F(0, 0)，天真地，这将涉及多次计算中间值，但通过缓存每个F(i, j)，如复制它，复杂性减少到O(n^2)。
这是一些快速而肮脏的c ++，它可以做到这一点：
#include <iostream>
#define INVALID -1
int max(int p, int q, int r)
{
return p >= q && p >= r ? p : q >= r ? q : r;
}
int F(int i, int j, int * a, int * b, int len, int * cache)
{
if (cache[i * (len + 1) + j] != INVALID)
return cache[i * (len + 1) + j];
int p = 0, q = 0, r = 0;
if (i < len && j < len)
p = a[i] * b[j] + F(i + 1, j + 1, a, b, len, cache);
if (i + 1 < len)
q = a[i] * a[i + 1] + F(i + 2, j, a, b, len, cache);
if (j + 1 < len)
r = b[j] * b[j + 1] + F(i, j + 2, a, b, len, cache);
return cache[i * (len + 1) + j] = max(p, q, r);
}
int main(int argc, char ** argv)
{
int a[] = {2, 1, 3};
int b[] = {3, 7, 9};
int len = 3;
int cache[(len + 1) * (len + 1)];
for (int i = 0; i < (len + 1) * (len + 1); i++)
cache[i] = INVALID;
cache[(len + 1) * (len + 1) - 1] = 0;
std::cout << F(0, 0, a, b, len, cache) << std::endl;
}
如果您需要实际的合并序列而不仅仅是总和，您还必须缓存选择了哪个p, q, r并回溯。
通过动态编程解决它的一种方法是始终存储：
S [i] [j] [l] =“合并A [1，...，i]和B [1，...，j]的最佳方法，如果l == 0，则最后一个元素是A [i]，如果l == 1，则最后一个元素是B [j]“。
然后，DP将是（伪代码，在A [0]和B [0]处插入任何数字，并且让实际输入在A [1] ... A [n]，B [1]中。 .B [N]）：
S[0][0][0] = S[0][0][1] = S[1][0][0] = S[0][1][1] = 0; // If there is only 0 or 1 element at the merged vector, the answer is 0
S[1][0][1] = S[0][1][1] = -infinity; // These two cases are impossible
for i = 1...n:
for j = 1...n:
// Note that the cases involving A[0] or B[0] are correctly handled by "-infinity"
// First consider the case when the last element is A[i]
S[i][j][0] = max(S[i-1][j][0] + A[i-1]*A[i], // The second to last is A[i-1].
S[i-1][j][1] + B[j]*A[i]); // The second to last is B[j]
// Similarly consider when the last element is B[j]
S[i][j][1] = max(S[i][j-1][0] + A[i]*B[j], // The second to last is A[i]
S[i][j-1][1] + B[j-1]*B[j]); // The second to last is B[j-1]
// The answer is the best way to merge all elements of A and B, leaving either A[n] or B[n] at the end.
return max(S[n][n][0], S[n][n][1]);
合并并对其进行排序。可能是合并排序。排序数组给出最大值。（合并只是附加数组）。复杂性是nlogn。
这是Clojure中的一个解决方案，如果你对一些偏僻的道路感兴趣的话。它是O（n3），因为它只生成所有n2稳定合并并花费n次时间对产品求和。与我见过的基于阵列的命令式解决方案相比，补偿和算术的麻烦要少得多，这有望使算法更加突出。而且它也非常灵活：例如，如果你想要包括c2 * c3以及c1 * c2和c3 * c4，你可以简单地用(partition 2 coll)替换(partition 2 1 coll)。
;; return a list of all possible ways to stably merge the two input collections
(defn stable-merges [xs ys]
(lazy-seq
(cond (empty? xs) [ys]
(empty? ys) [xs]
:else (concat (let [[x & xs] xs]
(for [merge (stable-merges xs ys)]
(cons x merge)))
(let [[y & ys] ys]
(for [merge (stable-merges xs ys)]
(cons y merge)))))))
;; split up into chunks of two, multiply, and add the results
(defn sum-of-products [coll]
(apply + (for [[a b] (partition 2 coll)]
(* a b))))
;; try all the merges, find the one with the biggest sum
(defn best-merge [xs ys]
(apply max-key sum-of-products (stable-merges xs ys)))
user> (best-merge [2 1 5] [3 7 9])
(2 1 3 5 7 9)
我认为如果你提供更多的测试用例会更好。但我认为两个数组的正常合并类似于合并排序中的合并将解决问题。
用于合并数组的伪代码在Wiki上给出。
基本上它是正常的
merging algorithm used in Merge Sort。在Merge sort中，对数组进行了排序，但是在这里我们对未排序的数组应用了相同的合并算法。
Step 0：让i成为first array(A)和j的指数是index for second array(B）。 i=0 , j=0
Step 1：Compare A[i]=2 & B[j]=3。从2<3开始，它将成为新的merged array(C)的第一个元素。 i=1, j=0（将该数字添加到较小的新数组中）
Step 2：再次Compare A[i]=1 and B[j]=3. 1<3因此insert 1 in C. i++, j=0;
Step 3：再次Compare A[i]=3 and B[j]=3。 Any number can go in C(both are same). i++, j=0;（基本上我们正在增加插入数字的数组的索引）
Step 4：因为array A is complete只是直接insert the elements of Array B in C。否则重复前面的步骤。
Array C = { 2, 1, 3, 3, 7,9}
我没有做过太多的研究。因此，如果有任何测试用例可能失败，请提供一个。