Tìm tổng số chênh lệch MAX và MIN của tất cả các tập con có thể

Question

Cho một tập hợp các phần tử, làm thế nào tôi có thể tìm thấy sự khác biệt giữa MAX và MIN trong tất cả các tập con của danh sách này.

Ví dụ:

set = 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

Sắp xếp danh sách.

Sau khi sắp xếp, phần tử thứ i sẽ là tối thiểu trong tất cả các tập con (và chỉ) không bao gồm các phần tử đầu tiên i-1 và không bao gồm phần tử này. Có 2^(n-i) trong số đó (khi i là 1 dựa).

Tương tự, i sẽ là yếu tố cao nhất trong mỗi tập con mà không bao gồm bất kỳ số sau i, và đừng bao gồm i, và có 2^(i-1) tập con như vậy (một lần nữa, 1 trụ sở).

Vì vậy, sau khi phân loại, chỉ cần lặp, và cho mỗi i add:

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

hiệu quả thêm số tiền bằng arr[i] * #times_i_is_max, và giảm nó bằng cách arr[i] * #times_i_is_min

Trong ví dụ của bạn:

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 

Nút cổ chai của thuật toán này là sắp xếp, là O(nlogn) - sau đó, mọi thứ được thực hiện trong quét tuyến tính của mảng.

Answer 2

@mukul bạn có thể tính toán tất cả các quyền hạn của 2 và lưu trữ chúng trong một mảng dùng mod đồng thời như

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