Medium · Dynamic Programming

Maximum Number of Points with Cost

Given an m × n integer matrix points, pick exactly one cell in every row. You gain the values of the picked cells and lose |c1 − c2| for each pair of consecutive rows picked at columns c1 and c2. Return the maximum total you can reach.

Examples

Example 1

[[1,2,3],[1,5,1],[3,1,1]]

Output: 9 points

Example 2

[[1,2,3],[1,5,1]]

Output: 7 points

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.