The largest sum

Computer Science Level 3

Given an unsorted array of numbers, compute the largest distinct pair sum in the array with only one traversal .

What is the largest distinct pair sum in the text .

Details and Assumptions

For example in the array $[5, 9, 9, 4, 7]$ the largest pair sum is $(9+7=16$ ).

The answer is 299.

1 solution

Vivek Sedani
Aug 23, 2015

You just need to find the largest and second largest integer in the array ( both distinct ). It is very easy to do it in a single iteration.

One might argue that it's not that easy to do it in a single iteration since the intuitive solution to this problem is of $O(n^2)$ time complexity.

Your solution seems more like a comment. You should consider editing it to make the solution helpful to others who were working on the problem.

Although, after poking around the problem for a bit, I managed to make a crude, yet $O(n)$ algorithm (i.e., works in one traversal) to get the answer. Here 's my solution in C++ in case anyone wants to take a look. I think the code there is pretty much self-explanatory.

Prasun Biswas - 5 years, 9 months ago

The largest sum

The answer is 299.

1 solution

0 pending reports