What is the main pattern used in Power of Heroes?

The problem uses state transition dynamic programming, updating cumulative sums as you iterate through sorted hero strengths.

How does sorting help in this problem?

Sorting ensures that the maximum of each subset is easily tracked, simplifying the DP calculation of each group's power.

Can we optimize space usage in this DP approach?

Yes, instead of storing a full DP array, a rolling variable can hold the previous cumulative contribution, reducing space to O(1).

Why do we need modulo 10^9 + 7?

The sum of powers can be extremely large, so modulo prevents integer overflow and keeps results within limits.

How does GhostInterview assist with subset DP problems?

It guides through computing each element's contribution to all subsets using DP, showing efficient state transitions and accumulation.

#2681

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

英雄的力量

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的力量定义为： i 0 ， i 1 ， ... i k 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[ i 0 ],nums[ i 1 ] ... nums[ i k ]) …

数组数学动态规划排序前缀和

题目描述

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的力量定义为：

i₀ ，i₁ ，... i_k 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i₀],nums[i₁] ... nums[i_k])² * min(nums[i₀],nums[i₁] ... nums[i_k]) 。

请你返回所有可能的非空英雄组的力量之和。由于答案可能非常大，请你将结果对 10⁹+ 7 取余。

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 2² * 2 = 8 。
第 2 组：[1] 的力量为 1² * 1 = 1 。
第 3 组：[4] 的力量为 4² * 4 = 64 。
第 4 组：[2,1] 的力量为 2² * 1 = 4 。
第 5 组：[2,4] 的力量为 4² * 2 = 32 。
第 6 组：[1,4] 的力量为 4² * 1 = 16 。
第 7 组：[2,1,4] 的力量为 4² * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 数学

我们注意到，题目中涉及到子序列的最大值和最小值，数组中元素的顺序不影响最终的结果，因此我们可以先对数组进行排序。

接下来，我们枚举每个元素作为子序列的最小值，不妨记数组的每个元素为 $a_1, a_2, \cdots, a_n$ 。以 $a_i$ 作为最小值的子序列的贡献为：

a_i \times (a_{i}^{2} + a_{i+1}^2 + 2 \times a_{i+2}^2 + 4 \times a_{i+3}^2 + \cdots + 2^{n-i-1} \times a_n^2)

我们注意到，每一个 $a_i$ 都会乘上 $a_i^2$ ，这一部分我们可以直接累加到答案中。剩下的部分，我们可以用一个变量 $p$ 来维护，初始时 $p = 0$ 。

接下来从右往左枚举 $a_i$ ，每次我们将 $a_i \times p$ 累加到答案中，然后令 $p = p \times 2 + a_i^2$ 。

枚举完所有的 $a_i$ 之后，返回答案即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        nums.sort()
        ans = 0
        p = 0
        for x in nums[::-1]:
            ans = (ans + (x * x % mod) * x) % mod
            ans = (ans + x * p) % mod
            p = (p * 2 + x * x) % mod
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) for sorting plus O(n) for DP iteration, giving O(n log n) overall. Space complexity is O(n) for storing DP states, though it can be optimized to O(1) with rolling variables.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting the array hints at a state transition dynamic programming solution.
question_mark
Watch for integer overflow in calculations; modulo is essential.
question_mark
Consider how each element contributes to all subsets including it.

warning

常见陷阱

外企场景

error
Failing to account for modulo during each addition can cause overflow.
error
Incorrectly calculating maximum or minimum in DP updates leads to wrong sums.
error
Assuming subsets are independent without considering cumulative state leads to inefficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute sum of hero group powers without modulo constraints, observing integer overflow.
arrow_right_alt
Find the maximum single group power instead of sum of all groups using the same DP pattern.
arrow_right_alt
Restrict groups to size k and sum powers using state transition DP optimized for fixed lengths.

help

常见问题

外企场景

继续练习

#2597 美丽子集的数目 #3250 单调数组对的数目 I #3251 单调数组对的数目 II