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

Ninja and Subarrays

Easy
0/40
Average time to solve is 20m
profile
Contributed by
45 upvotes
Asked in companies
MicrosoftInfosys

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 5
2 <= N <= 10^5
1 <= A[i] <= 10^4

Time Limit: 1 sec.
Sample Input 1:
2
4
1 2 3 4
2
3 8
Sample Output 1:
7
11
Explanation For Sample Output 1:
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. 
Sample Input 2:
2
5
8 3 7 2 4
4
6 4 7 5
Sample Output 2:
11
12
Full screen
Console