You are given two arrays each with n integers. Find the maximum sum of two elements. You have to choose one element from the first array, one element from the second array and their indexes have to be different.
A greedy algorithms doesn't work, it has to be a dynamic one and with a complexity of O(n).
Conceptually, this is how I would approach this problem:
Find the biggest and the 2nd biggest element of each array, and keep track of which index they're in. This should be O(n) each.
After you do that, check all the possible sums you can make out of these four numbers(2 from each array) where the index of each isn't the same. This will be your biggest sum. This will take a constant amount of time, and won't affect your time complexity.