Maximum points tourist can earn

Array Dynamic Programming Matrix

47.5% acceptance

Feb 23, 2026

You are given two integers, n and k, along with two 2D integer arrays, stayScore and travelScore. A tourist is visiting a country with n cities, where each city is directly connected to every other city. The tourist's journey consists of exactly k 0-indexed days, and they can choose any city as their starting point. Each day, the tourist has two choices: Stay in the current city: If the tourist stays in their current city curr during day i, they will earn stayScore[i][curr] points. Move to another city: If the tourist moves from their current city curr to city dest, they will earn travelScore[curr][dest] points. Return the maximum possible points the tourist can earn.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(n: i32, k: i32, stay_score: Vec<Vec<i32>>, travel_score: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let k = k as usize;
    let neg_inf = i32::MIN / 2;
    
    // dp[city] = max score ending at city after day i
    let mut dp = vec![0i32; n];
    
    for day in 0..k {
      let mut ndp = vec![neg_inf; n];
      for curr in 0..n {
        if dp[curr] == neg_inf { continue; }
        // Stay
        let stay = dp[curr] + stay_score[day][curr];
        ndp[curr] = ndp[curr].max(stay);
        // Travel
        for dest in 0..n {
          if dest == curr { continue; }
          let travel = dp[curr] + travel_score[curr][dest];
          ndp[dest] = ndp[dest].max(travel);
        }
      }
      dp = ndp;
    }
    
    *dp.iter().max().unwrap()
  }
}