One iteration

Easy

0/40

Average time to solve is 10m

Contributed by

38 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

13
8

Explanation for Sample Input 1:

In the first test case, Bob can select the 1st and 4th elements leading to a sum of 13.
In the second test case, there are only two elements, so Bob has to select both of them, so the final sum is 8.

Sample Input 2:

2
5 
-9 2 3 10 9
3 
-12 4 -10

Sample Output 2:

19
-6

Hint 1

Hint 2

Can we check all possible combinations of taking two elements?

Approaches (2)

Approach 1

Approach 2

Brute Force

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’’

Time Complexity

O(N ^ 2), where ‘N’ is the size of the array.

Since we are using two nested loops to find all possible pairs, so the total time complexity is O(N ^ 2).

Space Complexity

O(1)

We are using constant extra space.

(100% EXP penalty)

One iteration

Console