diff options
-rw-r--r-- | max_num_point_cost.c | 46 | ||||
-rw-r--r-- | max_num_point_cost.py | 52 |
2 files changed, 98 insertions, 0 deletions
diff --git a/max_num_point_cost.c b/max_num_point_cost.c new file mode 100644 index 0000000..8f1e97a --- /dev/null +++ b/max_num_point_cost.c @@ -0,0 +1,46 @@ +// 1937. Maximum Number of Points with Cost +#include "leetcode.h" + +/* + * you are given an 'm * n' integer matrix 'points' (0 indexed). starting with 0 + * points you want to maximise the numbber of points you can get from the + * matrix. 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. 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', picking cells + * at coordinates '(r, c_1)' and '(r + 1, c_2)' will subtract 'abs(c_1 - c_2)' + * from your score. return the maximum number of points you can achieve + */ + +long long maxPoints(int **points, int pointsSize, int *pointsColSize) { + long long *pre = (long long *)malloc(*pointsColSize * sizeof(int)); + long long *left = (long long *)calloc(*pointsColSize, sizeof(long long)); + long long *right = (long long *)calloc(*pointsColSize, sizeof(long long)); + long long *curr = (long long *)calloc(*pointsColSize, sizeof(long long)); + for (int i = 0; i < *pointsColSize; i++) + pre[i] = points[0][i]; + for (int i = 0; i < pointsSize - 1; ++i) { + left[0] = pre[0]; + right[*pointsColSize - 1] = pre[*pointsColSize - 1]; + for (int j = 1; j < *pointsColSize; ++j) + left[j] = fmax(left[j - 1] - 1, pre[j]); + for (int j = *pointsColSize - 2; j >= 0; --j) + right[j] = fmax(right[j + 1] - 1, pre[j]); + for (int j = 0; j < *pointsColSize; ++j) + curr[j] = points[i + 1][j] + fmax(left[j], right[j]); + pre = curr; + } + long long ans = 0; + for (int i = 0; i < *pointsColSize; i++) + ans = fmax(ans, pre[i]); + free(pre), free(left), free(right), free(curr); + return ans; +} + +int main() { + int p1[3][3] = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}}, + p2[3][2] = {{1, 5}, {2, 3}, {4, 2}}, pcs1[] = {3, 3, 3}, + pcs2[] = {2, 2, 2}; + printf("%lld\n", maxPoints((int **)p1, ARRAY_SIZE(p1), pcs1)); // expect: 9 + printf("%lld\n", maxPoints((int **)p2, ARRAY_SIZE(p2), pcs2)); // expect: 11 +} diff --git a/max_num_point_cost.py b/max_num_point_cost.py new file mode 100644 index 0000000..3e40ba9 --- /dev/null +++ b/max_num_point_cost.py @@ -0,0 +1,52 @@ +# 1937. Maximum Number of Points with Cost + +""" +you are given an 'm * n' integer matrix 'points' (0 indexed). starting with 0 +points you want to maximise the numbber of points you can get from the +matrix. 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. 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', picking cells +at coordinates '(r, c_1)' and '(r + 1, c_2)' will subtract 'abs(c_1 - c_2)' +from your score. return the maximum number of points you can achieve +""" + + +class Solution(object): + def maxPoints(self, points): + """ + :type points: List[List[int]] + :rtype: int + """ + m, n = len(points), len(points[0]) + if m == 1: + return max(points[0]) + if n == 1: + return sum(sum(x) for x in points) + + def left(arr): + left = [arr[0]] + [0] * (n - 1) + for i in range(1, n): + left[i] = max(left[i - 1] - 1, arr[i]) + return left + + def right(arr): + right = [0] * (n - 1) + [arr[-1]] + for i in range(n - 2, -1, -1): + right[i] = max(right[i + 1] - 1, arr[i]) + return right + + pre = points[0] + for i in range(m - 1): + left, right, curr = left(pre), right(pre), [0] * n + for j in range(n): + curr[j] = points[i + 1][j] + max(left[j], right[j]) + pre = curr[:] + + return max(pre) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxPoints(points=[[1, 2, 3], [1, 5, 1], [3, 1, 1]])) + print(obj.maxPoints(points=[[1, 5], [2, 3], [4, 2]])) |