如何从所有可能的子阵列中找到最小和次最小元素的最大和

Question

给定一个数组，求从所有可能的子数组中选择的最小元素和次最小元素的最大和。更正式地说，如果我们写出大小为

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

这个问题是关于GFG的，但我不理解它的解释。

请任何人给出它在O（n）时间复杂度下的解。

Answer 1

首先你不明白这个问题！如果你仔细考虑所有的子数组，最后你可以看到所有的子数组都是相关的；换句话说，我们正在考虑以前的子数组到当前子数组的结果

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

从每个子数组：

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.

因此，检查数组中的每一对值可以降低总体复杂性

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)

总体复杂度：O（N）。

Answer 2

问题是：如果我们只看长度为2的所有子阵列，为什么我们总是保证找到最大和？

为了回答这个问题，让我们假设我们有一些数组A。在该数组中，显然，必须至少有一个子数组S，其中最小和第二小的元素，让我们称之为X和Y，求和我们的结果。

如果这两个元素已经相邻，这意味着有一个长度为2的a的子阵列将包含X和Y，因此，如果我们只查看长度为2的所有子阵列，我们将找到X和Y并输出X Y。

然而，问题是：有没有办法让我们的两个元素X和Y在S中不成为“邻居”？好吧，如果是这样的话，显然需要其他号码，我们叫它们Z0，Z1。。。，在他们之间。

显然，对于所有这些值，它必须保持Zi

如果任何一个Zi大于X或Y，这就意味着a的子阵列将只包括这个更大的Zi加上它的邻居。在这个子数组中，Zi和它的邻居将是最小和次最小的元素，它们的总和将大于X Y，因此我们的子数组S不会是给出我们的解的子数组。这与我们对S的定义相矛盾，所以这不可能发生。

所以，所有的Zi不能小于X或Y，也不能大于X或Y。这只剩下一种可能性：对于X==Y，它们都可以相等。但是，在这种情况下，我们显然还有一个长度为2的子数组，它总结了我们的正确结果。

因此，在所有情况下，我们都可以证明必须有一个长度为2的子数组，其中两个元素的总和就是我们的结果，这就是为什么该算法是正确的。