Sum of maximum elements of all subsets - GeeksforGeeks

Sum of maximum elements of all subsets - GeeksforGeeks
Given an array of integer numbers, we need to find sum of maximum number of all possible subsets.

A simple solution is to iterate through all subsets of array and finding maximum of all of them and then adding them in our answer, but this approach will lead us to exponential time complexity.

An efficient solution is based on one thing, how many subsets of array have a particular element as their maximum. As in above example, four subsets have 5 as their maximum, two subsets have 3 as their maximum and one subset has 2 as its maximum. The idea is to compute these frequencies corresponding to each element of array. Once we have frequencies, we can just multiply them with array values and sum them all, which will lead to our final result.
To find frequencies, first we sort the array in non-increasing order and when we are standing at a[i] we know, all element from a[i + 1] to a[N-1] are smaller than a[i], so any subset made by these element will choose a[i] as its maximum so count of such subsets corresponding to a[i] will be, 2^(N – i – 1) (total subset made by array elements from a[i + 1] to a[N]). If same procedure is applied for all elements of array, we will get our final answer as,
res = a[0]*2^(N-1) + a[1]*2^(N-2) ….. + a[i]*2^(N-i-1) + ….. + a[N-1]*2^(0)
Now if we solve above equation as it is, calculating powers of 2 will take time at each index, instead we can reform the equation similar to horner’s rule for simplification,
res = a[N] + 2*(a[N-1] + 2*(a[N-2] + 2*( …… 2*(a[2] + 2*a[1])…..))))
Total complexity of above solution will be O(N*log(N))

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;

}

This code does not work if array will have repeating elements. So first elements should be inserted into HashSet(Java) consequently each element will occur single time only. And then the above operation should be performed.

Read full article from Sum of maximum elements of all subsets - GeeksforGeeks