algorithm - 从两个数组中选择一对

Question

给定2个长度分别为n和m的数组A和B。

我想找到一对 (A[i],B[j]) 使得总和 A[i]+B[j] 最大，但条件是 j-i>k 对于给定的整数 k 和 1 < = 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 中选择第二个元素和从 B 中选择第六个元素。

希望能把问题说清楚

Answer 1

这是在 O(N+M) 中完成的方法:-

生成一个max数组，其中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 = -infinity;


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

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

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

  }

}