1937. 扣分后的最大得分Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分减少 abs(c1 - c2) 。

请你返回你能得到的最大得分。

abs(x) 定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。

示例 1：

screenshot-2021-07-12-at-13-40-26-diagram-drawio-diagrams-net.png 输入：points = [[1,2,3],[1,5,1],[3,1,1]] 输出：9 解释：蓝色格子是最优方案选中的格子，坐标分别为 (0, 2)，(1, 1) 和 (2, 0) 。你的总得分增加 3 + 5 + 3 = 11 。但是你的总得分需要扣除 abs(2 - 1) + abs(1 - 0) = 2 。你的最终得分为 11 - 2 = 9 。示例 2：

screenshot-2021-07-12-at-13-42-14-diagram-drawio-diagrams-net.png 输入：points = [[1,5],[2,3],[4,2]] 输出：11 解释：蓝色格子是最优方案选中的格子，坐标分别为 (0, 1)，(1, 1) 和 (2, 0) 。你的总得分增加 5 + 3 + 4 = 12 。但是你的总得分需要扣除 abs(1 - 1) + abs(1 - 0) = 1 。你的最终得分为 12 - 1 = 11 。

提示：

m == points.length
n == points[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= points[r][c] <= 10⁵

# 思路

Math.max

# 解法

class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long ans = 0;
        long dp[] = new long[n];
        for(int i = 0;i < m;i++){
            long tmp[] = new long[n];
            long lmax = 0;
            for(int j = 0;j < n;j++){
                lmax = Math.max(lmax-1,dp[j]);
                tmp[j] = Math.max(lmax,tmp[j]);
            }
            long rmax = 0;
            for(int j = n-1;j >= 0;j--){
                rmax = Math.max(rmax-1,dp[j]);
                tmp[j] = Math.max(rmax,tmp[j]);
            }
            for(int j = 0;j < n;j++){
                tmp[j] += points[i][j];
                ans = Math.max(tmp[j],ans);
            }
            dp = tmp.clone();
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 总结

分析出几种情况，然后分别对各个情况实现

#Java