Maximize the minimum game score

Array Binary Search Greedy

26.1% acceptance

Mar 10, 2026

You are given an array points of size n and an integer m. There is another array gameScore of size n, where gameScore[i] represents the score achieved at the ith game. Initially, gameScore[i] == 0 for all i. You start at index -1, which is outside the array (before the first position at index 0). You can make at most m moves. In each move, you can either: Increase the index by 1 and add points[i] to gameScore[i]. Decrease the index by 1 and add points[i] to gameScore[i]. Note that the index must always remain within the bounds of the array after the first move. Return the maximum possible minimum value in gameScore after at most m moves.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(points: Vec<i32>, m: i32) -> i64 {
    let n = points.len();
    let m = m as i64;

    if m < n as i64 {
      return 0;
    }

    let can = |val: i64| -> bool {
      let mut total: i64 = 0;
      let mut transfer: i64 = 0;
      let mut skip_add: i64 = 0;
      for i in 0..n {
        if total > m {
          break;
        }
        let point = points[i] as i64;
        let necessary = (val + point - 1) / point;
        if transfer >= necessary {
          transfer = 0;
          skip_add += 1;
        } else {
          let p = transfer * point;
          let ops = (val - p + point - 1) / point;
          total += 2 * ops - 1;
          total += skip_add;
          transfer = (ops - 1).max(0);
          skip_add = 0;
        }
      }
      total <= m
    };

    let mut l: i64 = 1;
    let mut r: i64 = 1_000_000_000_000_000_000;
    let mut ans: i64 = 0;
    while l <= r {
      let mid = l + (r - l) / 2;
      if can(mid) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    ans
  }
}