961. Points With Penalty
A treasure hunter walks through m rooms laid out as the rows of points, and every room has n chests, one per column. In each room exactly one chest must be opened, and opening the chest in column c of row r earns points[r][c]. Walking between rooms costs effort: if the chest opened in one room is in column c1 and the chest opened in the next room is in column c2, you lose |c1 - c2| points.
Return the maximum total (points earned minus effort lost) over all valid choices. Rows and columns are 0-indexed.
Example 1
- Input:
- points = [[3,1,2],[1,5,1]]
- Output:
- 7
- Explanation:
Picking column 0 (3) then column 1 (5) loses 1 for the column gap: 3 + 5 - 1 = 7, which beats the alternatives 6 and 6.
Example 2
- Input:
- points = [[4,0],[0,4]]
- Output:
- 7
- Explanation:
Take 4 in row 0 and 4 in row 1 from different columns, minus a gap of 1, giving 7 (staying in one column would give only 4).
Example 3
- Input:
- points = [[2,9,4]]
- Output:
- 9
- Explanation:
With a single row there is no gap penalty, so the best cell, 9, is chosen.
Constraints
- 1 ≤ m, n
- m * n ≤ 105
- 0 ≤ points[r][c] ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(m * n)
- Space
- O(n)