python3 解法, 执行用时: 828 ms, 内存消耗: 39.1 MB, 提交时间: 2023-07-01 14:03:37

'''
对于所有上一行左边的数，都是加上它的坐标减去自己的坐标；
对于上一行所有右边的数，都是减去它的坐标加上自己的坐标；
分别求最大值即可。
'''
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m = len(points)
        n = len(points[0])
        dp = points[0]
        for i in range(1, m):
            new_dp = list(dp)
            left_max = -inf
            right_max = -inf
            for j in range(n):
                left_max = max(left_max, dp[j] + j)
                right_max = max(right_max, dp[n-1-j] - (n - 1 - j))
                new_dp[j] = max(left_max - j + points[i][j], new_dp[j])
                new_dp[n-1-j] = max((n - 1 - j) + right_max + points[i][n-1-j], new_dp[n-1-j])
            dp = new_dp
        return max(dp)

java 解法, 执行用时: 8 ms, 内存消耗: 66.2 MB, 提交时间: 2023-07-01 14:02:57

/**
 * dp[i][j]表示第i行第j列的元素所能得到的最大分数
 * dp[i][j] = max(dp[i - 1][k] + abs(k - j))
 * 
 **/
class Solution {
    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[] dp = new long[n];
        for (int i = 0; i < m; i++) {
            long[] cur = new long[n + 1];
            long lmax = 0;
            for (int j = 0; j < n; j++) {
                lmax = Math.max(lmax - 1, dp[j]);
                cur[j] = lmax;
            }
            long rmax = 0;
            for (int j = n - 1; j >= 0; j--) {
                rmax = Math.max(rmax - 1, dp[j]);
                cur[j] = Math.max(cur[j], rmax);
            }
            for (int j = 0; j < n; j++) {
                dp[j] = cur[j] + points[i][j];
            }
        }
        long ans = 0;
        for (int j = 0; j < n; j++) {
            ans = Math.max(ans, dp[j]);
        }
        return ans;
    }
}

golang 解法, 执行用时: 192 ms, 内存消耗: 18.4 MB, 提交时间: 2023-07-01 14:00:53

func maxPoints(points [][]int) int64 {
	ans := 0
	n := len(points[0])
	f := make([][2]int, n)  // f[i][j] 前i行中，第i行选择points[i][j]的最大得分
	sufMax := make([]int, n) // 后缀最大值
	for i, row := range points {
		if i == 0 {
			for j, v := range row {
				ans = max(ans, v)
				f[j][0] = v + j
				f[j][1] = v - j
			}
		} else {
			preMax := math.MinInt32
			for j, v := range row {
				preMax = max(preMax, f[j][0])
				res := max(v-j+preMax, v+j+sufMax[j]) // 左侧和右侧的最大值即为选择 points[i][j] 时的计算结果
				ans = max(ans, res) // 直接更新答案，这样下面就不直接存储 res 了，改为存储 res + j 和 res - j
				f[j][0] = res + j
				f[j][1] = res - j
			}
		}
		// 计算完一整行 f 后，对于每个位置 j，计算其右侧的所有 f[k] - k 的最大值
		// 这可以通过倒着遍历 f 求出
		sufMax[n-1] = f[n-1][1]
		for j := n - 2; j >= 0; j-- {
			sufMax[j] = max(sufMax[j+1], f[j][1])
		}
	}
	return int64(ans)
}

func max(a, b int) int { if a > b { return a }; return b }