What is the key pattern used in Maximize Value of Function in a Ball Passing Game?

The main pattern is state transition dynamic programming, combined with binary lifting to efficiently compute scores for large k.

Can I use a simple loop to compute the total score?

A simple loop works for small k but is too slow for large k, making binary lifting necessary for efficiency.

What is binary lifting in this context?

Binary lifting precomputes 2^j-th receiver jumps and sums so we can calculate k passes in O(log k) time instead of iterating all passes.

How do I handle cycles in the receiver array?

Use precomputed jump tables and cumulative sums; cycles are automatically handled because each jump considers prior sums up to powers of two.

What are the space and time limits I should watch?

Time complexity is O(n*log k) and space complexity is O(n*log k), sufficient for n up to 105 and k up to 1010.

#2836

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

在传球游戏中最大化函数值

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。总共有 n 名玩家，玩家编号互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏， receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给…

数组动态规划位运算

题目描述

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家编号互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之和，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver^(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			2
1	2	1	3
2	1	0	3
3	0	2	5
4	2	1	6

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			4
1	4	3	7
2	3	2	9
3	2	1	10

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

1 <= receiver.length == n <= 10⁵
0 <= receiver[i] <= n - 1
1 <= k <= 10¹⁰

lightbulb

解题思路

方法一：动态规划 + 倍增

题目要我们寻找从每个玩家 $i$ 开始，传球 $k$ 次内所有接触过球玩家的编号之和的最大值。如果暴力求解，需要从 $i$ 开始向上遍历 $k$ 次，时间复杂度为 $O(k)$ ，显然会超时。

我们可以使用动态规划，结合倍增的思想来处理。

我们定义 $f[i][j]$ 表示从玩家 $i$ 开始，传球 $2^j$ 次所能到达的玩家编号，定义 $g[i][j]$ 表示从玩家 $i$ 开始，传球 $2^j$ 次所能到达的玩家编号之和（不包括最后一个玩家）。

当 $j=0$ 是，传球次数为 $1$ ，所以 $f[i][0] = receiver[i]$ ，而 $g[i][0] = i$ 。

当 $j \gt 0$ 时，传球次数为 $2^j$ ，相当于从玩家 $i$ 开始，传球 $2^{j-1}$ 次，再从玩家 $f[i][j-1]$ 开始，传球 $2^{j-1}$ 次，所以 $f[i][j] = f[f[i][j-1]][j-1]$ ，而 $g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1]$ 。

接下来，我们可以枚举每个玩家 $i$ 作为开始玩家，然后根据 $k$ 的二进制表示，累计向上查询，最终得到玩家 $i$ 开始，传球 $k$ 次内所有接触过球玩家的编号之和的最大值。

时间复杂度 $O(n \times \log k)$ ，空间复杂度 $O(n \times \log k)$ 。其中 $n$ 为玩家数。

相似题目：

1483. 树节点的第 K 个祖先

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        n, m = len(receiver), k.bit_length()
        f = [[0] * m for _ in range(n)]
        g = [[0] * m for _ in range(n)]
        for i, x in enumerate(receiver):
            f[i][0] = x
            g[i][0] = i
        for j in range(1, m):
            for i in range(n):
                f[i][j] = f[f[i][j - 1]][j - 1]
                g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1]
        ans = 0
        for i in range(n):
            p, t = i, 0
            for j in range(m):
                if k >> j & 1:
                    t += g[p][j]
                    p = f[p][j]
            ans = max(ans, t + p)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n _log k) due to binary lifting jumps across k passes, and space complexity is O(n_ log k) for storing precomputed jump indices and cumulative sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to immediately consider large k and how naive iteration is too slow.
question_mark
Look for recognition of repeating patterns in passes and how they enable state transitions.
question_mark
Signals that candidate knows binary lifting or DP optimizations indicate readiness for hard array-DP problems.

warning

常见陷阱

外企场景

error
Attempting simple loop simulation results in timeouts for large k.
error
Overlooking the need to sum indices correctly when cycles occur in the receiver array.
error
Neglecting space optimization for precomputed jump tables during binary lifting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return both the maximum score and the starting player achieving it.
arrow_right_alt
Modify the problem to allow different scores for each player instead of their index.
arrow_right_alt
Constrain k to smaller values and compare naive simulation vs DP approach performance.

help

常见问题

外企场景

继续练习

#2920 收集所有金币可获得的最大积分 #2741 特别的排列 #2708 一个小组的最大实力值