Znalezienie sumy różnic wartości MAX i MIN wszystkich możliwych podzbiorów

Question

W zależności od zestawu elementów, w jaki sposób można znaleźć różnicę między wartościami MAX i MIN we wszystkich podzestawach tej listy.

Np

zestaw = 1 2 3

Subset = {1}, max(s)-min(s) = 0. 
Subset = {2}, max(s)-min(s) = 0. 
Subset = {3}, max(s)-min(s) = 0. 
Subset = {1,2}, max(s)-min(s) = 1. 
Subset = {2,3}, max(s)-min(s) = 1. 
Subset = {1,3}, max(s)-min(s) = 2. 
Subset = {1,2,3}, max(s)-min(s) = 2. 

So the output will be 1+1+2+2 = 6 

Answer 1

Sortowanie listy.

Po sortowaniu, pierwszy element będzie minimalny we wszystkich (i tylko) podzbiorach, które nie zawierają pierwszych elementów i-1 i uwzględnia ten element. Jest ich 2^(n-i) (gdy i ma wartość 1).

Podobnie i będzie najwyższym elementem każdej podgrupy, które nie zawierają żadnego numeru, po i i zawierają i i są 2^(i-1) takie podzbiory (również na podstawie 1).

Więc, po sortowaniu, po prostu iteracyjne, a dla każdego i dodają:

arr[i] * (2^(i-1) - 2^(n-i)) 

Skutecznie dodając sumę przez arr[i] * #times_i_is_max oraz zmniejszenie go przez arr[i] * #times_i_is_min

W przykładzie:

sorted=1,2,3 
1* (2^0 - 2^2) + 2*(2^1 - 2^1) + 3*(2^2 - 2^0) = 
1*(-3) + 2*0 + 3*(3) = -3 + 0 + 9 = 6 

Węzłem tego algorytmu jest sortowanie, czyli O(nlogn) - po tym wszystkim wszystko jest gotowe w liniowym skanowaniu tablicy.

Answer 2

@mukul można obliczyć wszystkie potęgi 2 i przechowywać je w tablicy biorąc mod jednocześnie jak

a[0]=1; for(i=1;i<any_no;i++)a[i]=(a[i-1]*2)%MOD;