Maximize value of function in a ball passing game

Array Dynamic Programming Bit Manipulation

30.4% acceptance

Feb 25, 2026

318

You are given an integer array receiver of length n and an integer k. n players are playing a ball-passing game. You choose the starting player, i. The game proceeds as follows: player i passes the ball to player receiver[i], who then passes it to receiver[receiver[i]], and so on, for k passes in total. The game's score is the sum of the indices of the players who touched the ball, including repetitions, i.e. i + receiver[i] + receiver[receiver[i]] + ... + receiver(k)[i]. Return the maximum possible score. Notes: receiver may contain duplicates. receiver[i] may be equal to i.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn get_max_function_value(receiver: Vec<i32>, k: i64) -> i64 {
    let n = receiver.len();
    let log = 34usize; // 2^34 > 10^10
    let mut lift = vec![vec![0usize; n]; log];
    let mut sum = vec![vec![0i64; n]; log];
    for i in 0..n {
      lift[0][i] = receiver[i] as usize;
      sum[0][i] = receiver[i] as i64;
    }
    for bit in 1..log {
      for i in 0..n {
        let mid = lift[bit-1][i];
        lift[bit][i] = lift[bit-1][mid];
        sum[bit][i] = sum[bit-1][i] + sum[bit-1][mid];
      }
    }
    let mut ans = 0i64;
    for start in 0..n {
      let mut score = start as i64;
      let mut pos = start;
      for bit in 0..log {
        if (k >> bit) & 1 == 1 {
          score += sum[bit][pos];
          pos = lift[bit][pos];
        }
      }
      ans = ans.max(score);
    }
    ans
  }
}