Ninja and Subarrays

Easy
0/40
Average time to solve is 20m
profile
Contributed by
46 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 )
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.
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
Hint

Try to find all the possible subarrays and hence the corresponding sum of the smallest and the second smallest elements of each subarray.

Approaches (2)
Brute-Force

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”.
  • Return the “ans”.
Time Complexity

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

Space Complexity

O(1).

 

Constant space is used.

Code Solution
(100% EXP penalty)
Ninja and Subarrays
Full screen
Console