合并两个数组，使所有奇数之和最大

Question

我有一个问题，给你两个数组，比如：

5 3
10 12 6 14 7
1 8 2

这意味着第一个数组中有5个数字，第二个数组中有3个数字。第二行是第一个数组，第三行是第二个数组。这个程序的目标是将第二个数组中的数字插入第一个数组（可以分开），从而使组合数组的所有位置都是奇数（第一、第三、第五……）数字加起来就是可能的最大数字。上述问题的输出示例：

44

既然阵列变成了

10 1 12 2 8 6 14 7
10+12+8+14=44

我试图利用第一个数组中的差异，通过

int[] diff=new int[numberinarray-1];
for(int i=0;i<numbersinarray-1;i++)
{
    diff[i]=firstarray[i]-firstarray[i+1];
}

并找到差异最大的地方在第二个数组中插入数字。但这种方式似乎非常无效，我仍然不确定如何真正做到这一点。我想知道有没有更简单、更高效的方法来做这道题。

Answer 1

为了将其表述为动态程序，我们可以将其视为从左到右合并两个数组。在每个步骤中，算法必须选择选择第一或第二列表的头部。假设两个输入序列是a和b，让S（i， j）是输出中奇数索引元素的总和，其中i是a的下一个可用元素>而j是b的下一个。然后呢

S(i,j) = if i+j is odd then max(a[i] + S(i-1,j), b[j] + S(i,j-1))
         else max(S(i-1,j), S(i,j-1)

注i j是所选输出位置的索引。

基本情况如下：

S(0,j) = if j is odd then b[j] + S(0,j-1) else S(0,j-1) [j>0]
S(i,0) = if i is odd then a[i] + S(i-1,0) else S(i-1,0) [i>0]
S(0,0) = max(S(0,1), S(1,0))