数组中最小值和次最小值的最大和-yiteyi-C++库

给定一个数组，找出从所有可能的子数组中选择的最小元素和次最小元素的最大和。更正式地说，如果我们写出大小>=2的数组的所有（nC2）子数组，并找到最小和次最小的和，那么我们的答案将是它们之间的最大和。例如：

Input : arr[] = [4, 3, 1, 5, 6]Output : 11Subarrays 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 = 6Maximum sum among all above choices is, 5 + 6 = 11Input : arr[] =  {5, 4, 3, 1, 6}Output : 9

null

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是生成所有子数组，求每个子数组的最小值和次最小值之和。最后返回所有总和的最大值。一 有效解决方案 是基于这样一个观察，即这个问题归结为寻找数组中两个连续元素的最大和。

如果（x，y）是一对，那么（x+y）就是答案，那么x和y必须是数组中的连续元素。

证据：

对于包含两个元素的子阵列，第一个和第二个最小元素就是这两个元素。

现在x和y出现在一些子阵列中，因此它们是端点。

现在，x，y必须是该子数组中最小的2个元素。如果还有其他元素Z _1. Z _2. , ……., Z _K 在x和y之间，它们大于或等于x和y，

案例1：

如果在x和y之间有一个元素z，那么包含元素max（x，y）和z的较小子阵列应该是答案，因为max（x，y）+z>=x+y

案例2：

如果x和y之间有多个元素，则x和y内的子阵列将具有所有连续元素（Z） _我 +Z _i+1 )>=（x+y），所以（x，y）对不是答案。

所以，根据矛盾，x和y必须是数组中连续的元素。

CPP

                         // 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

                         // 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                       

Python3

                         # 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#

                         // 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                       
                         // 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

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

输出：

时间复杂度：O（n）感谢Md Mishfaq Ahmed提出这种方法。本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END