Minimum of Maximum of Addition of two vectors/arrays

Question

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays.

Now you move the second array one field to the right. Now you can compute the maximum again of the intersection ... You can move the secound array $k$ times. I want to find the minimal maximum.

In the Example the maximum would be:

• $12$ for the first
• $13$ for the second
• $14$ for the third

so the first one is the best

Is there a efficient way to compute it or a efficient heuristic? (The faster the better even if it is a acceptable heuristic)

Answer 1

the bruteforce way would be to compute the maximum of all shifts and compare them. But i need to find a faster way (even it is heuristically and not too bad). As an output i only need the number of shifts where the maximum is minimal. I thought about taking the mean of both arrays and add them up and take the first list which has a maximum below or equal to the mean, but this does not work well.

Answer 2

Given an array $X = \{x_1, \dots,x_n\}$, let $Y = aux(X)$ be an array such that, $$y_1 = 1, y_i = \begin{cases} 1, & \mbox{if } y_i \geq y_{i-1} \\ 0, & \mbox{if } y_i < y_{i-1} \end{cases}$$

Let $A$ and $B$ be the two arrays given to you, compute $A' = aux(A)$ and $B' = reverse(aux(reverse(B))$.

Algorithm:

1. shift = 0
2. minMaxSum = Inf
3. $(sum, a_i, b_i) = \textrm{MaxSum}(A, B, shift)$
4. if $\max(a_i, b_i) == a_i$, then
   1. for (k = i-1; k >= 1; k--) if (B'[k] == 1) shift++; else break;
5. if $\max(a_i, b_i) == b_i$, then
   1. for (k = i+1; k <= n; k++) if (A'[k] == 1) shift++; else break;
6. minMaxSum = min(minMaxSum, sum)
7. if shift == n - 1, then STOP else GOTO step 2

Essentially, this gives a way of skipping over shifts. In the example that you gave,

A' = {1,1,1,1,1,1,1} and B' = {0,0,1,1,0,1,1}

In the first iteration, sum = 12, a_i = 3, b_i = 9. Since, max(a_i, b_i) = 9. We look at A' after position of value 3 and keep skipping shift as long as we keep seeing a 1. In this case, shift becomes n-1 in the first iteration itself. minMaxSum is set to 12.

The algorithm STOPS after first iteration, with the minMaxSum value as 12.

Thus we avoided computing sums for all shifts.

Of course, there are worst case scenario for this algorithm, for example consider what happens when $A$ is descending order and $B$ is ascending order. In general, when $A'$ has 1's at the beginning and many 0's at the end and/or $B'$ has many 0's at the beginning and 1's at the end, you may not get any benefit from this algorithm. However, these worst scenarios can be identified heuristically and we can solve an equivalent problem by

1. Let temp = reverse(A)
2. A = reverse(B)
3. B = temp

and solving for minMaxSum for this case. Again, the algoritm will start giving improvements once you do this.