Find the maximum amount of two sorted arrays

Question

There are two sorted array Aand Bthe same length, which Ais sorted in ascending order, and the array Bis sorted in descending order.

A = {1, 3, 7, 7, 7, 7}
B = {7, 7, 5, 5, 5, 4}

My task is to find two elements: one of Aand the other of B, so that their sum is maximum.

There is a limitation that I can select any element from A, but I need to select an element from Bin such a way that the index of the array element is Bgreater than the index of the element selected A.

In this case, the maximum amount that can be selected is 12. I did it in O(n), just repeating from left to right.

I want to know if there is a better and more efficient way to find the sum of these two elements.

Answer 1

We know that the best amount is the highest value among the sequence Cobtained by adding Aand Bpairwise.

Aand Bare monotonous, but Ccan be arbitrary, so there is no shortcut, you need to calculate everything C, but it O(N)is optimal.

Answer 2

As Yves Daust points out, in principle O (n) is optimal, but you can do some simple tricks to save time in practice.

You can use the maximum value of A.

const int maxA = A[sizeA-1];

, (i - ).

// since B will be smaller the next time and A is at its max, no need to go further
if ( A[i] >= maxA ) break; 

// if there is no chance left, to find a greater sum, since even maxA with the biggest
// B we are about to see is not big enough, break.
if ( maxA + B[i] <= currentMax ) break;