Back to Leetcode

Readme

Others/2681.Power-of-Heroes/Readme.md

latest881 B
Original Source

2681.Power-of-Heroes

我们将所有元素排序之后,假设nums[i]是所选子集的最大值,那么意味着子集的其他元素必然是在[0:i-1]里面选择。我们依次枚举最小值的话,那么所有子集的最小值的和

sum = nums[0]* 2^(i-2) + nums[1] * 2^(i-1) + ... + nums[i-1]* 2^0;

别忘了nums[i]本身也可以是最小值(子集只有一个元素)。所以答案就是sum * nums[i]^2 + nums[i] * nums[i]^2

当我们右移i,考虑新的nums[i]是所选自己的最大值时,sum依然是

sum = nums[0]* 2^(i-2) + nums[1] * 2^(i-1) + ... + nums[i-1]* 2^0;

和之前的sum相比,变动就是sum = (sum + nums[i-1]) * 2,o(1)时间就可以更新sum。

所以本题的算法就是:排序后,假设nums[i]是所选子集的最大值,更新sum,然后最终答案加上sum * nums[i]^2 + nums[i] * nums[i]^2