aboutsummaryrefslogtreecommitdiff
path: root/max_num_point_cost.c
blob: 8f1e97a4d0fa53750d2d6c4d792a628a7544cff4 (plain)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
}