1937. Maximum Number of Points with Cost Medium

1/**
2 * [1937] Maximum Number of Points with Cost
3 *
4 * 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.
5 * 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.
6 * 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.
7 * Return the maximum number of points you can achieve.
8 * abs(x) is defined as:
9 * 
10 * 	x for x >= 0.
11 * 	-x for x < 0.
12 * 
13 *  
14 * Example 1: 
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-40-26-diagram-drawio-diagrams-net.png" style="width: 300px; height: 300px;" />
16 * Input: points = [[1,2,3],[1,5,1],[3,1,1]]
17 * Output: 9
18 * Explanation:
19 * The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
20 * You add 3 + 5 + 3 = 11 to your score.
21 * However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
22 * Your final score is 11 - 2 = 9.
23 * 
24 * Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-42-14-diagram-drawio-diagrams-net.png" style="width: 200px; height: 299px;" />
26 * Input: points = [[1,5],[2,3],[4,2]]
27 * Output: 11
28 * Explanation:
29 * The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
30 * You add 5 + 3 + 4 = 12 to your score.
31 * However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
32 * Your final score is 12 - 1 = 11.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	m == points.length
38 * 	n == points[r].length
39 * 	1 <= m, n <= 10^5
40 * 	1 <= m * n <= 10^5
41 * 	0 <= points[r][c] <= 10^5
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximum-number-of-points-with-cost/
47// discuss: https://leetcode.com/problems/maximum-number-of-points-with-cost/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn max_points(points: Vec<Vec<i32>>) -> i64 {
53        
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1937() {
65    }
66}
67