所有子集的最大元素之和-yiteyi-C++库

给定一个整数数组，我们需要找到所有可能子集的最大数之和。 例如：

null

Input  : arr = {3, 2, 5}Output : 28Explanation : Subsets and their maximum are,{}            maximum = 0{3}             maximum = 3{2}            maximum = 2{5}            maximum = 5{3, 2}            maximum = 3{3, 5}            maximum = 5{2, 5}            maximum = 5{3, 2, 5}        maximum = 5Sum of maximum will be, 0 + 3 + 2 + 5 + 3 + 5 + 5 + 5 = 28,which will be our answer.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 就是遍历数组的所有子集，找到它们的最大值，然后将它们添加到我们的答案中，但这种方法会导致我们的时间复杂度呈指数级增长。一 有效解决方案 基于一件事，数组的多少子集有一个特定元素作为其最大值。如上例所示，四个子集的最大值为5，两个子集的最大值为3，一个子集的最大值为2。其思想是计算这些频率对应于阵列的每个元素。一旦我们有了频率，我们就可以将它们与数组值相乘，然后将它们相加，这将导致我们的最终结果。为了找到频率，首先我们以非递增的顺序对数组进行排序，当我们站在[i]时，我们知道，从[i+1]到[N-1]的所有元素都小于[i]，因此这些元素生成的任何子集都将选择[i]作为其最大值，因此对应于[i]的此类子集的计数将为，2^（N–i–1）（由[i+1]到[N]的数组元素生成的总子集）。如果对数组的所有元素应用相同的过程，我们将得到最终的答案， res=a[0]*2^（N-1）+a[1]*2^（N-2）…+a[i]*2^（N-i-1）+a[N-1]*2^（0）现在，如果我们按原样解上面的方程，计算每个指数的2次幂需要时间，相反，我们可以像霍纳法则为了简化， res=a[N]+2*（a[N-1]+2*（a[N-2]+2*（……2*（a[2]+2*a[1]）…）上述解决方案的总复杂度为O（N*log（N））

C++

                         // C/C++ code to find sum of maximum of all subsets of array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Method returns sum of maximum of all subsets                       
                         int                                     sumOfMaximumOfSubsets(                                     int                                     arr[],                                     int                                     N)                       
                         {                       
                                                 //    sorting array in decreasing order                       
                                                 sort(arr, arr + N, greater<                                     int                                     >());                       
           
                                                 //    initializing sum with first element                       
                                                 int                                     sum = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < N; i++)                       
                                                 {                       
                                                 // calculating evaluation similar to horner's rule                       
                                                 sum = 2 * sum + arr[i];                       
                                                 }                       
           
                                                 return                                     sum;                       
                         }                       
           
                         // Driver code to test above methods                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {3, 2, 5};                       
                                                 int                                     N =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << sumOfMaximumOfSubsets(arr, N) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.Arrays;                       
                         import                                     java.util.Collections;                       
           
                         // Java code to find sum of                       
                         // maximum of all subsets of array                       
                         class                                     GFG                       
                         {                       
           
                                                 // Method returns sum of maximum of all subsets                       
                                                 static                                     int                                     sumOfMaximumOfSubsets(Integer arr[],                                     int                                     N)                       
                                                 {                       
                                                 // sorting array in decreasing order                       
                                                 Arrays.sort(arr, Collections.reverseOrder());                       
           
                                                 // initializing sum with first element                       
                                                 int                                     sum = arr[                                     0                                     ];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < N; i++)                       
                                                 {                       
                                                 // calculating evaluation similar to horner's rule                       
                                                 sum =                                     2                                     * sum + arr[i];                       
                                                 }                       
           
                                                 return                                     sum;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 Integer arr[] = {                                     3                                     ,                                     2                                     ,                                     5                                     };                       
                                                 int                                     N = arr.length;                       
                                                 System.out.println(sumOfMaximumOfSubsets(arr, N));                       
                                                 }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Python3

                         # Python 3 code to find sum                       
                         # of maximum of all subsets                       
                         # of array                       
           
                         # Method returns sum of                       
                         # maximum of all subsets                       
                         def                                     sumOfMaximumOfSubsets(arr, N):                       
           
                                                 # sorting array in                       
                                                 # decreasing order                       
                                                 arr.sort(reverse                                     =                                     True                                     )                       
           
                                                 # initializing sum                       
                                                 # with first element                       
                                                 sum                                     =                                     arr[                                     0                                     ]                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , N):                       
                                   
                                                 # calculating evaluation                       
                                                 # similar to horner's rule                       
                                                 sum                                     =                                     2                                     *                                     sum                                     +                                     arr[i]                       
           
                                                 return                                     sum                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     3                                     ,                                     2                                     ,                                     5                                     ]                       
                         N                                     =                                     len                                     (arr)                       
                         print                                     (sumOfMaximumOfSubsets(arr, N))                       
           
                         # This code is contributed                       
                         # by Smitha                       

C#

                         // C# code to find sum of                       
                         // maximum of all subsets of array                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Method returns sum of maximum of all subsets                       
                                                 static                                     int                                     sumOfMaximumOfSubsets(                                     int                                     []arr,                                     int                                     N)                       
                                                 {                       
                                                 // sorting array in decreasing order                       
                                                 Array.Sort(arr);                       
                                                 Array.Reverse(arr);                       
           
                                                 // initializing sum with first element                       
                                                 int                                     sum = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < N; i++)                       
                                                 {                       
                                                 // calculating evaluation                       
                                                 // similar to horner's rule                       
                                                 sum = 2 * sum + arr[i];                       
                                                 }                       
           
                                                 return                                     sum;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []arr = {3, 2, 5};                       
                                                 int                                     N = arr.Length;                       
                                                 Console.WriteLine(sumOfMaximumOfSubsets(arr, N));                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

PHP

                         <?php                       
                         // PHP code to find sum of maximum of                       
                         // all subsets of array                       
           
                         // Method returns sum of maximum of all subsets                       
                         function                                     sumOfMaximumOfSubsets(                                     $arr                                     ,                                     $N                                     )                       
                         {                       
                                                 // sorting array in decreasing order                       
                                                 rsort(                                     $arr                                     );                       
           
                                                 // initializing sum with first element                       
                                                 $sum                                     =                                     $arr                                     [0];                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $N                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // calculating evaluation similar                       
                                                 // to horner's rule                       
                                                 $sum                                     = 2 *                                     $sum                                     +                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 return                                     $sum                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (3, 2, 5);                       
                         $N                                     =                                     count                                     (                                     $arr                                     );                       
                         echo                                     sumOfMaximumOfSubsets(                                     $arr                                     ,                                     $N                                     );                       
           
                         // This code is contributed by Rajput-Ji                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript code to find sum of                       
                         // maximum of all subsets of array                       
           
                         // Method returns sum of maximum of all subsets                       
                         function                                     sumOfMaximumOfSubsets(arr,N)                       
                         {                       
                                                 // sorting array in decreasing order                       
                                   
                                                 arr.sort((a,b)=>a-b);                       
                                                 arr.reverse();                       
                                                 // initializing sum with first element                       
                                                 let sum = arr[0];                       
                                                 for                                     (let i = 1; i < N; i++)                       
                                                 {                       
                                                 // calculating evaluation similar to horner's rule                       
                                                 sum = 2 * sum + arr[i];                       
                                                 }                       
           
                                                 return                                     sum;                       
                         }                       
           
           
                                                 let arr= [3, 2, 5];                       
                                                 let N = arr.length;                       
                                                 document.write(sumOfMaximumOfSubsets(arr, N));                       
                                   
                         </script>                       

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章