1937. Maximum Number of Points with Cost
有m*n的矩阵
要在每一列的挑一个数字，将这些数字相加
若是上下两列的行数不同就要减去行数差
假设是points[r1][c1]、points[r1+1][c2]
就要减去abs(c1,c2)
请问可以得到的最大总和是多少?
思路:
没想法的话
可以先去看这一题1014. Best Sightseeing Pair
用一个dp矩阵去纪录
其中dp[i]代表这一列第i行最大的总和
就由左到右和由右到左去去纪录最大值
maxnum=max(maxnum-1,points[i])
这样就可以得到答案了
golang code :
func maxPoints(points [][]int) int64 {
n, m := len(points), len(points[0])
maxtoright, maxtoleft := 0, 0
dp := make([]int, m)
for i := 0; i < n-1; i++ {
maxtoright, maxtoleft = 0, 0
for j := 0; j < m; j++ {
maxtoleft = max(maxtoleft-1, points[i][m-j-1])
maxtoright = max(maxtoright-1, points[i][j])
dp[j] = max(dp[j], maxtoright)
dp[m-1-j] = max(dp[m-1-j], maxtoleft)
}
for j := 0; j < m; j++ {
points[i+1][j] += dp[j]
}
}
ans := 0
for i := 0; i < m; i++ {
ans = max(ans, points[n-1][i])
}
return int64(ans)
}
func max(i, j int) int {
if i > j {
return i
}
return j
}