Last Updated: 26 Oct, 2021
Ninja and Subarrays
Easy
Asked in company
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.
Input Format:
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.
Constraints:
1 <= T <= 5
2 <= N <= 10^5
1 <= A[i] <= 10^4
Time Limit: 1 sec.
Approaches
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:
- Declare a variable “ans” to store the answer and initialize it to 0.
- Start iterating from 0 to (‘N’ - 2) using variable “start” which will denote the starting index of the corresponding subarray.
- Declare two variables, “smallest” and the “secondSmallest” to represent the smallest and the second smallest element of the current subarray.
- Initialize the “smallest” to ‘A[start]’ and the “secondSmallest” to INT_MAX.
- Start iterating from (“start” + 1) using variable “end” which will denote the ending index of the corresponding subarray.
- If ‘A[end]’ is less than the “smallest”.
- Set “secondSmallest” to “smallest”.
- Set “smallest” to ‘A[end]’.
- Else if ‘A[end]’ is less than the “secondSmallest”.
- Set “secondSmallest” to ‘A[end]’.
- Update “ans” as the maximum of itself and the sum of “smallest” and “secondSmallest”.
- If ‘A[end]’ is less than the “smallest”.
- Return the “ans”.
Observe that it is sufficient to consider the subarrays of size 2 only. To prove this let’s consider a subarray of size 3 [x y z] which gives the optimal answer, that means the smallest and the second smallest elements are x and z(because if x and y are the smallest and the second smallest elements then [x y] will also give the optimal answer. Similar is the case with y and z). Now y should be greater than both x and z. That means the subarray [y z] will have a greater sum than [x y z] because in the first one we will consider y and z but in the second one, we will consider x and z and y > x.
Algorithm:
- Declare a variable “ans” to store the answer and initialize it to 0.
- Start iterating from 1 to (‘N’ - 1).
- Update “ans” as the maximum of itself and the sum of the current and the previous elements.
- Return the “ans”.
Similar problems