How to find maximum sum of smallest and second smallest elements chosen from all possible subarrays

Question

Given an array, find maximum sum of smallest and second smallest elements chosen from all possible subarrays. More formally, if we write all (nC2) subarrays of array of size >=2 and find the sum of smallest and second smallest, then our answer will be maximum sum among them.

Examples: Input : arr[] = [4, 3, 1, 5, 6] Output : 11`

Subarrays with smallest and second smallest are,
[4, 3]        smallest = 3    second smallest = 4
[4, 3, 1]    smallest = 1    second smallest = 3
[4, 3, 1, 5]    smallest = 1    second smallest = 3
[4, 3, 1, 5, 6]    smallest = 1    second smallest = 3
[3, 1]         smallest = 1    second smallest = 3
[3, 1, 5]     smallest = 1    second smallest = 3
[3, 1, 5, 6]    smallest = 1    second smallest = 3
[1, 5]        smallest = 1    second smallest = 5
[1, 5, 6]    smallest = 1    second smallest = 5
[5, 6]         smallest = 5    second smallest = 6
Maximum sum among all above choices is, 5 + 6 = 11

This question is on GFG but I didn't understand its explanation.

Please anybody gives its solution in O(n) time complexity.

Answer 1

At first place you didn't understand the question! if you consider all sub-arrays carefully, at the end you can see all sub-arrays are related; in other words we are considering the result of previous sub-array into the current sub-array

Subarrays with smallest and second smallest are,
[4, 3]        smallest = 3    second smallest = 4
[4, 3, 1]    smallest = 1    second smallest = 3
[4, 3, 1, 5]    smallest = 1    second smallest = 3
[4, 3, 1, 5, 6]    smallest = 1    second smallest = 3
[3, 1]         smallest = 1    second smallest = 3
[3, 1, 5]     smallest = 1    second smallest = 3
[3, 1, 5, 6]    smallest = 1    second smallest = 3
[1, 5]        smallest = 1    second smallest = 5
[1, 5, 6]    smallest = 1    second smallest = 5
[5, 6]         smallest = 5    second smallest = 6
Maximum sum among all above choices is, 5 + 6 = 11

From each subarray:

1. we are taking the current largest value and if it is greater than previous largest we are replacing, and previous largest eventually becomes second most largest.
2. we are repeating this steps for every possible subarray (increasing in terms of index).
3. and at the end you can see, we are taking first-most and second-most value from the array.

so checking every-pair of values from the array reduced your overall complexity in O(N)

int res = arr[0] + arr[1];  //O(1)+O(1)
for (int i=1; i<N-1; i++)   // O(N-2) -> O(N)
   res = max(res, arr[i] + arr[i+1]); //O(1)+O(1)+O(1)

Overall complexity: O(N).

Answer 2

The question is: Why are we guaranteed to always find the maximum sum if we only look at all subarrays of length two?

To answer that question, lets assume we have some array A. Inside that array, obviously, there has to be at least one subarray S for which the smallest and second smallest elements, let's call them X and Y, sum up to our result.

If these two elements are already next to each other, this means that there is a subarray of A of length two that will contain X and Y, and thus, if we only look at all the subarrays of length two, we will find X and Y and output X+Y.

However, the question is: Is there any way for our two elements X and Y to not be "neighbors" in S? Well, if this was the case, there obviously would need to be other numbers, lets call them Z0, Z1, ..., between them.

Obviously, for all these values, it would have to hold that Zi >= X and Zi >= Y, because in S, X and Y are the smallest and second smallest elements, so there can be no other numbers smaller than X or Y.

If any of the Zi were bigger than X or Y, this would mean that there would be a subarray of A that only included this bigger Zi plus its neighbor. In this subarray, Zi and its neighbor would be the smallest and second smallest elements, and they would sum up to a larger sum than X+Y, so our subarray S would not have been the subarray giving us our solution. This is a contradiction to our definition of S, so this can not happen.

So, all the Zi can not be smaller than X or Y, and they can not be bigger than X or Y. This only leaves one possibility: For X == Y, they could all be equal. But, in this case, we obviously also have a subarray of length 2 that sums up to our correct result.

So, in all cases, we can show that there has to be a subarray of length two where both elements sum up to our result, which is why the algorithm is correct.