给定一个未排序的不同整数，找出其中最大的对和。例如，{12,34,10,6,40}中的最大对和是74。 难度等级：新手 预期时间复杂度：O（n）[一个数组只允许遍历一次]
null
这个问题主要归结为寻找数组中的最大和第二大元素。通过遍历数组一次，我们可以在O（n）时间内找到最大值和第二大值。
1) Initialize the first = Integer.MIN_VALUE second = Integer.MIN_VALUE2) Loop through the elements a) If the current element is greater than the first max element, then update second max to the first max and update the first max to the current element. 3) Return (first + second)
以下是上述算法的实现：
C++
// C++ program to find largest pair sum in a given array #include <iostream> using namespace std; /* Function to return largest pair sum. Assumes that there are at-least two elements in arr[] */ int findLargestSumPair( int arr[], int n) { // Initialize first and second largest element int first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and find first and second // largest elements in overall array for ( int i = 2; i < n; i++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then * update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } /* Driver program to test above function */ int main() { int arr[] = { 12, 34, 10, 6, 40 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Max Pair Sum is " << findLargestSumPair(arr, n); return 0; } |
JAVA
public class LargestPairSum { public static void main(String[] args) { // TODO Auto-generated method stub int arr[] = { 12 , 34 , 10 , 6 , 40 }; System.out.println(largestPairSum(arr, arr.length)); } private static int largestPairSum( int [] arr, int n) { int j = 0 ; int max = n == 1 ? arr[ 0 ] + arr[ 1 ] : arr[ 0 ]; for ( int i = 0 ; i < n; i++) { int sum = arr[j] + arr[i]; if (sum > max) { max = sum; if (arr[j] < arr[i]) { j = i; } } } return max; } } /** * This code is contributed by Tanveer Baba */ |
Python3
# Python3 program to find largest # pair sum in a given array # Function to return largest pair # sum. Assumes that there are # at-least two elements in arr[] def findLargestSumPair(arr, n): # Initialize first and second # largest element if arr[ 0 ] > arr[ 1 ]: first = arr[ 0 ] second = arr[ 1 ] else : first = arr[ 1 ] second = arr[ 0 ] # Traverse remaining array and # find first and second largest # elements in overall array for i in range ( 2 , n): # If current element is greater # than first then update both # first and second if arr[i] > first: second = first first = arr[i] # If arr[i] is in between first # and second then update second elif arr[i] > second and arr[i] ! = first: second = arr[i] return (first + second) # Driver program to test above function */ arr = [ 12 , 34 , 10 , 6 , 40 ] n = len (arr) print ( "Max Pair Sum is" , findLargestSumPair(arr, n)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to find largest // pair sum in a given array using System; class GFG { /* Method to return largest pair sum. Assumes that there are at-least two elements in arr[] */ static int findLargestSumPair( int [] arr) { // Initialize first and // second largest element int first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and // find first and second largest // elements in overall array for ( int i = 2; i < arr.Length; i++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } // Driver Code public static void Main() { int [] arr1 = new int [] { 12, 34, 10, 6, 40 }; Console.Write( "Max Pair Sum is " + findLargestSumPair(arr1)); } } |
PHP
<?php // PHP program to find largest // pair sum in a given array // Function to return largest // pair sum. Assumes that // there are at-least two // elements in arr[] */ function findLargestSumPair( $arr , $n ) { // Initialize first and // second largest element $first ; $second ; if ( $arr [0] > $arr [1]) { $first = $arr [0]; $second = $arr [1]; } else { $first = $arr [1]; $second = $arr [0]; } // Traverse remaining array // and find first and second // largest elements in overall // array for ( $i = 2; $i < $n ; $i ++) { // If current element is greater // than first then update both // first and second if ( $arr [ $i ] > $first ) { $second = $first ; $first = $arr [ $i ]; } // If arr[i] is in between first // and second then update second else if ( $arr [ $i ] > $second and $arr [ $i ] != $first ) $second = $arr [ $i ]; } return ( $first + $second ); } // Driver Code $arr = array (12, 34, 10, 6, 40); $n = count ( $arr ); echo "Max Pair Sum is " , findLargestSumPair( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find largest // pair sum in a given array /* Method to return largest pair sum. Assumes that there are at-least two elements in arr[] */ function findLargestSumPair(arr) { // Initialize first and // second largest element let first, second; if (arr[0] > arr[1]) { first = arr[0]; second = arr[1]; } else { first = arr[1]; second = arr[0]; } // Traverse remaining array and // find first and second largest // elements in overall array for (let i = 2; i < arr.length; i ++) { /* If current element is greater than first then update both first and second */ if (arr[i] > first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] > second && arr[i] != first) second = arr[i]; } return (first + second); } let arr1 = [12, 34, 10, 6, 40]; document.write( "Max Pair Sum is " + findLargestSumPair(arr1)); // This code is contributed by divyeshrabadiy07. </script> |
输出
Max Pair Sum is 74
上述解的时间复杂度为O（n）。 上述解的空间复杂度为O（1）。
本文由 里沙布 并通过 阿克什塔帕特尔酒店 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
