Reach end of array with max score

Array Greedy

33.4% acceptance

Feb 25, 2026

225

You are given an integer array nums of length n. Your goal is to start at index 0 and reach index n - 1. You can only jump to indices greater than your current index. The score for a jump from index i to index j is calculated as (j - i) * nums[i]. Return the maximum possible total score by the time you reach the last index.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximum_score(nums: Vec<i32>) -> i64 {
    // Key insight: if we're at position i, we earn nums[i] per step until we jump.
    // Optimal: jump when we reach a larger value. So total = sum of (next_larger_idx - i) * nums[i].
    // Greedy: scan left to right, accumulate max_val seen so far times 1 per step.
    let n = nums.len();
    let mut total = 0i64;
    let mut max_val = nums[0] as i64;
    for i in 1..n {
      total += max_val;
      if nums[i] as i64 > max_val {
        max_val = nums[i] as i64;
      }
    }
    total
  }
}