Last Updated: 17 Nov, 2021

One iteration

Easy

Asked in companies

Solve now

Problem statement

Alice loves to give challenging tasks to Bob. This time, Alice gave Bob an array ‘A’ of ‘N’ distinct integers and asked him to find the maximum sum Bob can make by taking two elements from this array. To make this challenging, Alice asked Bob to find the answer by traversing the array only once.

As always, Bob asked you to help him do the task by traversing the array only once.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains one integer ‘N’, denoting the size of the array.

The following line contains an array ‘A’ of ‘N’ spaced distinct integers.

Output Format:

For each test case, print a single integer in a new line denoting the maximum sum Bob can make by taking two integers from the array.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 5
2 <= N <= 10^5
-10^9 <= A[i] <= 10^9 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We need to take two elements from the array so that their sum is maximum. To do this, we can use two nested loops to check all possible pairs and store the maximum possible sum.

Algorithm:

Initialise ‘ans’ to INT_MIN.
Run a loop ‘i’ from 0 to ‘N’ - 1
- Run a loop ‘j’ from ‘i’ + 1 to ‘N’ - 1
- Update ‘ans’ to the maximum of ‘ans’ and ‘A[i]’ + ‘A[j]’
Return ‘ans’’

Solve now

02 Approach

We need to find the array’s maximum and second maximum values in a single traversal. Let’s use two variables, to store the array’s maximum and second maximum values.

A few key observations are :

Whenever we reach any element having a greater value than the current maximum value, the current maximum value becomes that value, and the current second maximum value becomes the previous maximum value.
Suppose we reach any element whose current value is smaller than the current maximum value but is bigger than the current second maximum value. In that case, we need to update the current second maximum value to that value.

Algorithm:

Initialize ‘mx’ and ‘smx’ to INT_MIN.
Run a loop ‘i’ from 0 to ‘N’ - 1
- If ‘A[i]’ is greater than ‘mx’
  - Update ‘smx’ to ‘mx’
  - Update ‘mx’ to ‘A[i]’
- Else if ‘A[i]’ is greater than ‘smx’
  - Update ‘smx’ to ‘A[i]’
Return ‘smx’ + ‘mx’

Solve now