如何找到数组所有可能子集的最大值和最小值之和 [英] How to find Sum of differences of maximum and minimum of all possible subset of an array

问题描述

如何查找给定数组的所有可能子集的最大值-最小值

例如

给定数组为1
所有可能的子集均为[[]，[1]]
1-1 = 0

given array is 1 all posible subsets are [[], [1]] 1-1=0

给定的数组为1 2
所有可能的子集为[[]，[1]，[2]，[1、2]]
1-1 + 2-2 + 2-1 = 1

given array is 1 2 all posible subsets are [[], [1], [2], [1, 2]] 1-1+2-2+2-1=1

给定数组为1 2 3
所有可能的子集为[ []，[1]，[2]，[1、2]，[3]，[1、3]，[2、3]，[1、2、3]]
1-1 + 2 -2 + 2-1 + 3-3 + 3-1 + 3-2 + 3-1 = 6

given array is 1 2 3 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 1-1+2-2+2-1+3-3+3-1+3-2+3-1=6

给定的数组为1 2 3 4
所有可能的子集为[[]，[1]，[2]，[1、2]，[3]，[1、3]，[4]，[2、3]，[ 1、4]，[1、2、3]，[2、4]，[1、2、4]，[3、4]，[1、3、4]，[2、3、4]，[ 1，2，3，4]]]
ans = 23

given array is 1 2 3 4 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [4], [2, 3], [1, 4], [1, 2, 3], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]] ans=23

给定数组为2 3 4 5
全部可能的子集是[[]，[1]，[2]，[1、2]，[3]，[1、3]，[4]，[2、3]，[1、4]，[5] ，[1、2、3]，[2、4]，[1、5]，[1、2、4]，[3、4]，[2、5]，[1、3、4]，[ 1，2，5]，[3，5]，[2， 3，4]，[1、3、5]，[4、5]，[1、2、3、4]，[2、3、5]，[1、4、5]，[1、2， 3、5]，[2、4、5]，[1、2、4、5]，[3、4、5]，[1、3、4、5]，[2、3、4、5] ，[1、2、3、4、5]]
ans = 72

given array is 2 3 4 5 all posible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [4], [2, 3], [1, 4], [5], [1, 2, 3], [2, 4], [1, 5], [1, 2, 4], [3, 4], [2, 5], [1, 3, 4], [1, 2, 5], [3, 5], [2, 3, 4], [1, 3, 5], [4, 5], [1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 2, 3, 5], [2, 4, 5], [1, 2, 4, 5], [3, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5], [1, 2, 3, 4, 5]] ans= 72

推荐答案

首先，排序数组，则第i个元素在所有不包含 i-1 第一个元素并包含此元素的子集中都是最小的。其中将有 2 ^（n-i）个。同样， i 将成为每个子集中的最高元素，其中 i 之后不包含任何数字，并且包括 i ，并且有 2 ^（i-1）这样的子集。现在对每个 i 添加：

First of all, sort the array then the i'th element will be minimum in all subsets that do not include the i-1 first elements, and include this element. There will be 2^(n-i) of those. In the same way, i will be the highest element in each subset that does not include any number after i, and include i, and there are 2^(i-1) such subsets.now iterate and for each i add:

sum = sum + array[i] * (2^(i) - 2^(n-i-1))
//if array starts with index array[0]

考虑您的示例： [1,2,3]

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

这篇关于如何找到数组所有可能子集的最大值和最小值之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！