从两个阵列中选择一对

给定2个阵列A和B，长度分别为n和m。从两个阵列中选择一对

我想找到一个对（A [i]，B [j]）使得和A [i] + B [j]最大，但是在给定的整数k和1的情况下，ji> k < = i < = n，1 < = j < = m。

我知道一个简单的O（n * m）天真的方法来解决它，但是他们有更好的方法来做到这一点。

让我举个例子说我们有两个数组A = [5,10,9,7,10]和B = [0,0,0,4,1,2，-2]并且说K = 3然后我必须从A和B中选择一个元素，使得所选元素的位置之间的差异至少为k。在这种情况下，我们可以看到ans是12.通过选择A中的第2个元素和B中的第6个元素。

希望它讲清楚明白的问题

来源

2013-12-09 user3080139

使用动态编程:)创建阵列MAXB与长度为m，指数MAXB i的指示从i到阵列B的米的最大值maxB可以通过maxB [i] = max（B [i]，maxB [i + 1]）在O（n）中容易地完成。那么你只需遍历A元素max = max（A [i] + maxB [i + k]，max）。复杂度是O（n） –

你可以通过上面的例子更清楚地说明吗？？Thnx。如何maxB可以在O（n）中完成。它应该是O（m）我猜 – user3080139

在你的例子中，maxB = {4,4,4,4,2,2，-2};因此从A = 1开始到5，我们有max = A [1] + maxB [1 +（K + 1）] = 9，那么对于i = 2，max = A [2] + maxB [2 + （K + 1）] = 12 ...我们有最大= 12 :) n是常数，所以应该是O（max（n，m）） –

这里是方式做到这一点在O(N+M)： -

生成最大阵列其中max [i]表示在子阵列b最大元素[I到M]

max[m] = b[m]   
for(i=m-1;i>=1;i--) 
    max[i] = maximum(max[i+1],b[i]);

对所有的有效对计算maxpair如下： -

maxpair = -infinity; 


for(i=1;i<=n;i++) { 

    if(i+k+1<=m) { 

    maxpair = maximum(maxpair,a[i]+max[i+k+1]); 

    } 

}

来源

2013-12-09 04:45:41

从两个阵列中选择一对

回答

相关问题