electroRF
Member
Hi,
Given an unsorted list of N numbers, what is the the non-neighbored pair with the largest sum.
Example: {3, 45, 1, 5, 94, 100}, N = 6
Answer: (100,45)
Obviously, we can do it in O(N^2) - i.e. for each number in the array, go through all the numbers except for its neighbor, and update MAX_SUM if needed.
Is there a more efficient solution?
Given an unsorted list of N numbers, what is the the non-neighbored pair with the largest sum.
Example: {3, 45, 1, 5, 94, 100}, N = 6
Answer: (100,45)
Obviously, we can do it in O(N^2) - i.e. for each number in the array, go through all the numbers except for its neighbor, and update MAX_SUM if needed.
Is there a more efficient solution?