How to determine the greatest sum of the smallest and second smallest items from all available subarrays

[Mobo01]

Find the largest sum of the lowest and second smallest items in an array from all available subarrays. In more technical terms, if we write all (nC2) subarrays of an array of size >=2 and determine the sum of the smallest and second smallest, our result will be the greatest total of 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 this website https://www.scaler.com/topics/largest-subarray-with-0-sum/ but I don't understand what it means. Please provide a solution of O(n) time complexity.

[jonnin]

but I don't understand what it means.

what do you not understand?

you drew the problem perfectly .. except that it can be optimized. Once it decreases, anything you add (by growing the current subarray) can't improve it.
so 4/3/1 array broke it, it was better at 4/3. Stop adding elements, and jump to
3/1 iteration (remember the 4/3, it could be your best, that is starting point and end point of best array found so far).

now you have to find a way to do it without brute force... do this on paper. The code is going to be very simple, the hard part is figuring out the trick of the question to do it without so much work.

[seeplus]

As a starter, this will produce the required sub-arrays (C++17), together with the 2 smallest numbers:

#include <vector>
#include <iostream>
#include <utility>
#include <limits>

std::pair<int, int> smallest(const std::vector<int>& arr) {
	int sec { std::numeric_limits<int>::max() }, first { sec };

	for (auto a : arr)
		if (a < first) {
			sec = first;
			first = a;
		} else if (a < sec)
			sec = a;

	return { first, sec };
}

void process(const std::vector<int>& arr) {
	std::cout << "[ ";
	for (const auto& a : arr)
		std::cout << a << ' ';

	const auto sm { smallest(arr) };

	std::cout << "]  smallest = " << sm.first << "  second smallest = " << sm.second << '\n';
}

void getSubArrays(const std::vector<int>& arr, size_t start = 0, size_t end = 0) {
	if (end != arr.size())
		if (start > end)
			getSubArrays(arr, 0, end + 1);
		else {
			if (end != start)
				process(std::vector<int> { arr.begin() + start, arr.begin() + end + 1 });

			getSubArrays(arr, start + 1, end);
		}
}

int main() {
	const std::vector arr { 4, 3, 1, 5, 6 };

	getSubArrays(arr);
}

[ 4 3 ]  smallest = 3  second smallest = 4
[ 4 3 1 ]  smallest = 1  second smallest = 3
[ 3 1 ]  smallest = 1  second smallest = 3
[ 4 3 1 5 ]  smallest = 1  second smallest = 3
[ 3 1 5 ]  smallest = 1  second smallest = 3
[ 1 5 ]  smallest = 1  second smallest = 5
[ 4 3 1 5 6 ]  smallest = 1  second smallest = 3
[ 3 1 5 6 ]  smallest = 1  second smallest = 3
[ 1 5 6 ]  smallest = 1  second smallest = 5
[ 5 6 ]  smallest = 5  second smallest = 6

[lastchance]

@Mobo1,
What question are you asking?

You say that you want "the greatest sum of the smallest and second smallest items from all available subarrays".

Yet you point us to "the largest subarray with zero sum"????

Surely "the greatest sum of the two smallest items over all subarrays" amounts to "the greatest sum of two adjacent elements", since, inductively, if you took any subarray then the addition of an element at either end to form a longer subarray would either keep the sum of the two smallest the same or would make it smaller. e.g. Consider going from [5,6] to [1,5,6] to [3,1,5,6] in the full example: the best sum goes down from 5+6 to 5+1 to 3+1 as we successively replace either of the two smallest. So, any length-2 array will always be as good or better than a length-3 one, which will be as good or better than a length-4 one etc.

You can easily do the "greatest sum of two adjacent elements" in O(N) simply by sweeping through the array.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int bestSumOfTwoSmallest( const vector<int> &V )      // Assumes V.size() >= 2;
{
   int best = V[0] + V[1];
   for ( int i = 2; i < V.size(); i++ ) best = max( best, V[i] + V[i-1] );
   return best;
}

int main()
{
   cout << bestSumOfTwoSmallest( { 4, 5, 6, 3, 1 } ) << '\n';
}

[salem c]

OP is a shill/repost bot for whatever website they're pushing.

The answer is on the site they quote, if they scrolled down far enough.

But they're not here to learn, only to farm the clicks.

[Ganado]

Huh, craftier than the usual POS bots. Thanks for the heads up.