Maximum Points Tourist Can Earn

Medium
1665.

Maximum Points Tourist Can Earn

Maximum Points Tourist Can Earn is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.

A tourist visits a country of n cities, every pair of which is connected by a direct road, for exactly k days (numbered from 0). The tourist may start in any city.

Each day, the tourist in city curr chooses one of two things:

  • Stay in curr and earn stayScore[i][curr] points on day i, or
  • Move to another city dest and earn travelScore[curr][dest] points.

Return the maximum total number of points the tourist can earn.

Example 1

Input
n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
Output
3
Explanation
Start in city 1 and stay there for the day.

Example 2

Input
n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]
Output
8
Explanation
Start in city 1, stay on day 0 (4 points) and move to city 2 on day 1 (4 points).

Example 3

Input
n = 1, k = 3, stayScore = [[5],[1],[7]], travelScore = [[0]]
Output
13
Explanation
With one city the tourist stays every day: 5 + 1 + 7.

Constraints

  • 1 <= n <= 200
  • 1 <= k <= 200
  • n == travelScore.length == travelScore[i].length == stayScore[i].length
  • k == stayScore.length
  • 1 <= stayScore[i][j] <= 100
  • 0 <= travelScore[i][j] <= 100
  • travelScore[i][i] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @param {number[][]} stayScore
 * @param {number[][]} travelScore
 * @return {number}
 */
var maxScore = function(n, k, stayScore, travelScore) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Points Tourist Can Earn — Problem & Solution

Maximum Points Tourist Can Earn solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Points Tourist Can Earn is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Matrix
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A tourist visits a country of n cities, every pair of which is connected by a direct road, for exactly k days (numbered from 0). The tourist may start in any city.

Each day, the tourist in city curr chooses one of two things:

  • Stay in curr and earn stayScore[i][curr] points on day i, or
  • Move to another city dest and earn travelScore[curr][dest] points.

Return the maximum total number of points the tourist can earn.

Example 1

Input: n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
Output: 3
Explanation: Start in city 1 and stay there for the day.

Example 2

Input: n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]
Output: 8
Explanation: Start in city 1, stay on day 0 (4 points) and move to city 2 on day 1 (4 points).

Example 3

Input: n = 1, k = 3, stayScore = [[5],[1],[7]], travelScore = [[0]]
Output: 13
Explanation: With one city the tourist stays every day: 5 + 1 + 7.

Constraints

  • 1 <= n <= 200
  • 1 <= k <= 200
  • n == travelScore.length == travelScore[i].length == stayScore[i].length
  • k == stayScore.length
  • 1 <= stayScore[i][j] <= 100
  • 0 <= travelScore[i][j] <= 100
  • travelScore[i][i] == 0

Hints for Maximum Points Tourist Can Earn

  1. Hint 1

    What matters at the end of a day is only which city the tourist is in — not how they got there.

  2. Hint 2

    Let dp[c] be the best total so far ending the day in city c. Before day 0 every city is a free starting point, so dp[c] = 0.

  3. Hint 3

    On day i, new[c] = max(dp[c] + stayScore[i][c], max over p != c of dp[p] + travelScore[p][c]).

How to solve Maximum Points Tourist Can Earn

Each day's choice depends only on the current city, so a DP over (day, city) captures every itinerary: the tourist ends day i in city c either by staying there or by moving in from another city.

Approach

  1. Set dp[c] = 0 for every city (the tourist may start anywhere).
  2. For each day i, compute new[c] = max(dp[c] + stayScore[i][c], max_{p != c} dp[p] + travelScore[p][c]).
  3. Replace dp with new; after k days return max(dp).

Why it works

The points earned on later days depend only on where the tourist is, so among all histories that end day i in city c, only the best total can lead to an optimal answer. The two cases (stay, move from some p) are exactly the ways to end a day in c.

Complexity

  • Time — O(k · n^2)
  • Space — O(n)

Pitfalls

  • Staying in c earns stayScore, not travelScore[c][c] (which is 0) — keep the move case to p != c.
  • The start city is free — no points are earned just for starting there.

Reference solution

Python

from typing import List

def maxScore(n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
    dp = [0] * n
    for day in range(k):
        stay = stayScore[day]
        nd = [0] * n
        for c in range(n):
            best = dp[c] + stay[c]
            for p in range(n):
                if p != c:
                    v = dp[p] + travelScore[p][c]
                    if v > best:
                        best = v
            nd[c] = best
        dp = nd
    return max(dp)

Java

public static int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
    int[] dp = new int[n];
    for (int day = 0; day < k; day++) {
        int[] nd = new int[n];
        for (int c = 0; c < n; c++) {
            int best = dp[c] + stayScore[day][c];
            for (int p = 0; p < n; p++) {
                if (p != c) best = Math.max(best, dp[p] + travelScore[p][c]);
            }
            nd[c] = best;
        }
        dp = nd;
    }
    int ans = 0;
    for (int v : dp) ans = Math.max(ans, v);
    return ans;
}

C++

int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
    vector<int> dp(n, 0);
    for (int day = 0; day < k; day++) {
        vector<int> nd(n, 0);
        for (int c = 0; c < n; c++) {
            int best = dp[c] + stayScore[day][c];
            for (int p = 0; p < n; p++) {
                if (p != c) best = max(best, dp[p] + travelScore[p][c]);
            }
            nd[c] = best;
        }
        dp = nd;
    }
    return *max_element(dp.begin(), dp.end());
}

JavaScript

var maxScore = function(n, k, stayScore, travelScore) {
    var dp = new Array(n).fill(0);
    for (var day = 0; day < k; day++) {
        var nd = new Array(n).fill(0);
        for (var c = 0; c < n; c++) {
            var best = dp[c] + stayScore[day][c];
            for (var p = 0; p < n; p++) {
                if (p !== c && dp[p] + travelScore[p][c] > best) best = dp[p] + travelScore[p][c];
            }
            nd[c] = best;
        }
        dp = nd;
    }
    var ans = 0;
    for (var i = 0; i < n; i++) if (dp[i] > ans) ans = dp[i];
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming