2Sum and variants

Question:
Given two arrays A and B:
- they are of the same length
- contain unsorted integers, maybe negatives, 0, or positives
- i is an index in A and j in B
- i < j
Find the max sum of A[i] + B[j].



Discussion:
We always have a method to solve algorithm problems if given no limit on time and space complexity. So I can start from a simple example and find out the way.
A = [0, -2,  3,  4, 9, 6]
     i
B = [9,  0, -2, -5, 4, 5]
         j
From this example, I can easily observe:
- the last element in A and the first element in B cannot be considered
- given i, we need to iterate j through (i, n) in B to calculate the max(A[i] + B[j])
- iterate i through [0, n). For each i, perform the last step
When i arrives at n, the max value is the result. The complexity is O(n^2) time and O(1) space.

Improvement 1:
We observe that one sub-problem is to find the max value in B from (i, n) by iterating j through B. Sounds familiar? Yes, we can use a max heap to accelerate this procedure at the cost of space. Initially, we build a max heap for B and remove B[i] from the heap as i moves forward in A. This will lead to O(nlgn) time and O(n) space for the max heap.

Improvement 2:
Can we do better? The reason why we have a max heap is because we need to extract the second max value from B[i + 2, n), after considering B[i + 1, n). The face value may be the same. We don't know this information without "sorting (heap or linear scan)" it. If I want to be sure about the second max value within constant time and space, I need to make sure all options have been considered in all previous rounds. This leads us to consider the iteration from the right to the left.

Instead of starting from A[0] and B[1], I can start from A[n - 2] and B[n - 1]. When j moves to the left, I check if B[j] is larger than the current max in B. If so, update the current max in B. Then we add current_max_B to A[i]. If this sum is larger than the current max sum, we update it. However, we never look back for A[i + 1, n), because we have already considered them.

We can also move j forward and maintain the max element so far in A. The time and space complexity are O(n) and O(1) respectively.

Follow up:
What if we have A, B, C and i < j < k?