Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

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 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.
```

Detailed explanation

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