Problem of the day
One day Ninja got an array and started to play with it. He is finding subarrays of the array randomly and suddenly starts to wonder about the maximum of the sum of the smallest and the second smallest elements of all the subarrays possible of size at least 2.
For Example:For the array [3 2 1]
All the subarrays of size at least 2 are:
[3 2], [2 1], [3 2 1]
For the first subarray, the smallest and second smallest elements are 2 and 3, and their sum is 5.
For the second subarray, the smallest and second smallest elements are 1 and 2, and their sum is 3.
For the third subarray, the smallest and second smallest elements are 1 and 2, and their sum is 3.
So the maximum among these sums is 5.
Since Ninja is too lazy to do this task, he asked you for help. You have to find the maximum of the sum of the smallest and the second smallest elements of all the subarray possible of size at least 2.
The first line will contain a single integer ‘T’ denoting the number of test cases. Then the test cases follow.
The first line of each test case will contain a single integer ‘N’, denoting the size of the array.
The second line of each test case will contain ‘N’ space-separated integers, denoting the elements of the array.
Output Format:
For each test case, print a single integer denoting the maximum of the sum of the smallest and the second smallest elements of all the subarray possible of size at least 2.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 5
2 <= N <= 10^5
1 <= A[i] <= 10^4
Time Limit: 1 sec.
2
4
1 2 3 4
2
3 8
7
11
For the first test case, all the possible subarrays of size at least 2 are:
[1 2], [1 2 3], [1 2 3 4], [2 3], [2 3 4], [3 4].
The respective sum of the smallest and second smallest elements are 3, 3, 3, 5, 5, 7.
So the answer will be the maximum of all of them, i.e., 7.
For the second test case, there is only one subarray possible [3 8]. So the answer will be 11.
2
5
8 3 7 2 4
4
6 4 7 5
11
12
Try to find all the possible subarrays and hence the corresponding sum of the smallest and the second smallest elements of each subarray.
We will find all the possible subarrays and then calculate the sum of the smallest and the second smallest elements of each subarray. Then we will take the maximum of all of them to find the answer.
Algorithm:
O(N^2), where ‘N’ is the size of the array.
Since we are considering all the possible subarrays and there are approximately N^2 subarrays, the total time complexity will be O(N^2).
O(1).
Constant space is used.