CODEWITHSUNDEEP
arraysalgorithm
vivek puri
vivek puri

Reputation: 59

Find the maximum sum out of two sorted arrays

There are two sorted arrays A and B of equal length where A is sorted in ascending order and array B is 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 from A and other from B, so that their sum is maximum.

There is a constraint that I can choose any element from A but I have to choose the element from B in such an order that the index of the element of array B should be greater than that of the chosen element of A.

In this case, the maximum sum that can be chosen is 12. I have done it in O(n) by simply iterating from left to right.

I want to know whether there exists any better and more efficient way to find the sum of those two elements.

Upvotes: 4

Views: 167

Answers (2)

Gombat
Gombat

Reputation: 2084

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

You can make usage of the maximum value of A.

const int maxA = A[sizeA-1];

In your loop, you can check the following two conditions to savely abort your loop searching for the maximum ( i is your loop variable).

// 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;

Upvotes: 0

user1196549
user1196549

Reputation:

We know that the best sum is the largest value among the sequence C obtained by adding A and B pairwise.

A and B are monotonic, but C can be arbitrary, so there is no shortcut, you need to compute the whole of C, and O(N) is optimal.

Upvotes: 5

Related Questions