Maximum number of points with cost

Array Dynamic Programming Matrix

41.8% acceptance

Feb 25, 2026

3257

241

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_points(points: Vec<Vec<i32>>) -> i64 {
    let n = points[0].len();
    let mut dp: Vec<i64> = points[0].iter().map(|&x| x as i64).collect();

    for row in &points[1..] {
      // Left pass: max(dp[j] + j) for j <= current col
      let mut left = vec![0i64; n];
      left[0] = dp[0];
      for j in 1..n {
        left[j] = left[j - 1].max(dp[j] + j as i64);
      }

      // Right pass: max(dp[j] - j) for j >= current col
      let mut right = vec![0i64; n];
      right[n - 1] = dp[n - 1] - (n - 1) as i64;
      for j in (0..n - 1).rev() {
        right[j] = right[j + 1].max(dp[j] - j as i64);
      }

      let mut new_dp = vec![0i64; n];
      for j in 0..n {
        new_dp[j] = row[j] as i64 + (left[j] - j as i64).max(right[j] + j as i64);
      }
      dp = new_dp;
    }
    *dp.iter().max().unwrap()
  }
}