Suma máxima del más pequeño y el segundo más pequeño en una array

Dada una array, encuentre la suma máxima de los elementos más pequeños y segundos más pequeños elegidos de todos los subarreglos posibles. Más formalmente, si escribimos todos los subarreglos (nC2) de un arreglo de tamaño >=2 y encontramos la suma del menor y el segundo menor, entonces nuestra respuesta será la suma máxima entre ellos. 

Ejemplos: 

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

Input : arr[] =  {5, 4, 3, 1, 6}
Output : 9

Una solución simple es generar todos los subarreglos, encontrar la suma del más pequeño y el segundo más pequeño de cada subarreglo. Finalmente devuelva el máximo de todas las sumas.

Una solución eficiente se basa en la observación de que este problema se reduce a encontrar una suma máxima de dos elementos consecutivos en una array. 

Si (x,y) es el par, tal que (x+y) es la respuesta, entonces x e y deben ser elementos consecutivos en la array.

Prueba:

Para un subarreglo con 2 elementos, el 1er y 2do elemento más pequeño son esos 2 elementos.

Ahora x e y están presentes en algún subarreglo de manera que son los puntos finales.

Ahora, x, y deben ser los 2 elementos más pequeños de ese subarreglo. Si hay otros elementos Z ₁ , Z ₂ , ……., Z _K  entre x e y, son mayores o iguales que x e y,

Caso 1 : 

• Si hay un elemento z entre x e y, entonces el subarreglo más pequeño con los elementos max(x,y) y z, debería ser la respuesta, porque max(x,y) + z >= x + y

Caso2:

• Si hay más de un elemento entre x e y, entonces el subarreglo dentro de x e y tendrá todos los elementos consecutivos (Z _i + Z _i+1 ) >= (x+y), por lo que el par (x,y) no puede t ser la respuesta. 
• Entonces, por contradicciones, x e y deben ser elementos consecutivos en la array.

Implementación:

// C++ program to get max sum with smallest
// and second smallest element from any subarray
#include <bits/stdc++.h>
using namespace std;
 
/*  Method returns maximum obtainable sum value
    of smallest and the second smallest value
    taken over all possible subarrays */
int pairWithMaxSum(int arr[], int N)
{
   if (N < 2)
     return -1;
 
   // Find two consecutive elements with maximum
   // sum.
   int res = arr[0] + arr[1];
   for (int i=1; i<N-1; i++)
      res = max(res, arr[i] + arr[i+1]);
 
   return res;
}
 
//  Driver code to test above methods
int main()
{
    int arr[] = {4, 3, 1, 5, 6};
    int N = sizeof(arr) / sizeof(int);
 
    cout << pairWithMaxSum(arr, N) << endl;
    return 0;
}

// Java program to get max sum with smallest
// and second smallest element from any subarray
import java.lang.*;
class num{
 
// Method returns maximum obtainable sum value
// of smallest and the second smallest value
// taken over all possible subarrays */
static int pairWithMaxSum(int[] arr, int N)
{
if (N < 2)
    return -1;
 
// Find two consecutive elements with maximum
// sum.
int res = arr[0] + arr[1];
for (int i=1; i<N-1; i++)
    res = Math.max(res, arr[i] + arr[i+1]);
 
return res;
}
 
// Driver program
public static void main(String[] args)
{
    int arr[] = {4, 3, 1, 5, 6};
    int N = arr.length;
    System.out.println(pairWithMaxSum(arr, N));
}
}
//This code is contributed by
//Smitha Dinesh Semwal

# Python 3 program to get max
# sum with smallest and second
# smallest element from any
# subarray
 
# Method returns maximum obtainable
# sum value of smallest and the
# second smallest value taken
# over all possible subarrays
def pairWithMaxSum(arr, N):
 
    if (N < 2):
        return -1
     
    # Find two consecutive elements with
    # maximum sum.
    res = arr[0] + arr[1]
     
    for i in range(1, N-1):
        res = max(res, arr[i] + arr[i + 1])
     
    return res
     
# Driver code
arr = [4, 3, 1, 5, 6]
N = len(arr)
 
print(pairWithMaxSum(arr, N))
 
# This code is contributed by Smitha Dinesh Semwal

// C# program to get max sum with smallest
// and second smallest element from any subarray
using System;
 
class GFG {
 
// Method returns maximum obtainable sum value
// of smallest and the second smallest value
// taken over all possible subarrays
static int pairWithMaxSum(int []arr, int N)
{
     
if (N < 2)
    return -1;
 
// Find two consecutive elements
// with maximum sum.
int res = arr[0] + arr[1];
for (int i = 1; i < N - 1; i++)
    res = Math.Max(res, arr[i] + arr[i + 1]);
 
return res;
}
 
// Driver code
public static void Main()
{
    int []arr = {4, 3, 1, 5, 6};
    int N = arr.Length;
    Console.Write(pairWithMaxSum(arr, N));
}
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to get max sum with smallest
// and second smallest element from any subarray
 
/* Method returns maximum
   obtainable sum value
   of smallest and the
   second smallest value
   taken over all possible
   subarrays */
function pairWithMaxSum( $arr, $N)
{
    if ($N < 2)
        return -1;
     
    // Find two consecutive
    // elements with maximum
    // sum.
    $res = $arr[0] + $arr[1];
    for($i = 1; $i < $N - 1; $i++)
        $res = max($res, $arr[$i] +
                    $arr[$i + 1]);
     
    return $res;
}
 
    // Driver Code
    $arr = array(4, 3, 1, 5, 6);
    $N = count($arr);
 
    echo pairWithMaxSum($arr, $N);
 
// This code is contributed by anuj_67.
?>

// javascript program to get max sum with smallest
// and second smallest element from any subarray
   
// Method returns maximum obtainable sum value
// of smallest and the second smallest value
// taken over all possible subarrays
 
function pairWithMaxSum(arr,  N)
{
       
if (N < 2)
    return -1;
   
// Find two consecutive elements
// with maximum sum.
 
var res = arr[0] + arr[1];
for (var i = 1; i < N - 1; i++)
    res = Math.max(res, arr[i] + arr[i + 1]);
   
return res;
}
   
// Driver code
 
    var arr = [4, 3, 1, 5, 6]
    var N = arr.length;
    document.write(pairWithMaxSum(arr, N));
 
// This code is contributed by bunnyram19.

11

Complejidad de tiempo : O(n)

Gracias a Md Mishfaq Ahmed por sugerir este enfoque.
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.