Sponsored
Sponsored
This approach uses dynamic programming where we keep track of the maximum points obtainable for each cell using two linear passes per row: one from left to right and the other from right to left. This ensures that we account for the cost of moving between rows efficiently.
Time Complexity: O(m * n) as we iterate through the cells twice per row. Space Complexity: O(n) due to the auxiliary arrays used.
1#include <stdio.h>
2#include <stdlib.h>
3
4int max(int a, int b) {
5 return a > b ? a : b;
6}
7
8int maxPoints(int** points, int pointsSize, int* pointsColSize) {
9 int m = pointsSize;
10 int n = *pointsColSize;
11 int* prevRow = (int*)malloc(sizeof(int) * n);
12
13 for (int j = 0; j < n; j++) {
14 prevRow[j] = points[0][j];
15 }
16
17 for (int i = 1; i < m; i++) {
18 int* leftToRight = (int*)malloc(sizeof(int) * n);
19 int* rightToLeft = (int*)malloc(sizeof(int) * n);
20 int* currentRow = (int*)malloc(sizeof(int) * n);
21
22 leftToRight[0] = prevRow[0];
23 for (int j = 1; j < n; j++) {
24 leftToRight[j] = max(leftToRight[j - 1] - 1, prevRow[j]);
25 }
26
27 rightToLeft[n - 1] = prevRow[n - 1];
28 for (int j = n - 2; j >= 0; j--) {
29 rightToLeft[j] = max(rightToLeft[j + 1] - 1, prevRow[j]);
30 }
31
32 for (int j = 0; j < n; j++) {
33 currentRow[j] = points[i][j] + max(leftToRight[j], rightToLeft[j]);
34 }
35
36 free(prevRow);
37 prevRow = currentRow;
38 free(leftToRight);
39 free(rightToLeft);
40 }
41
42 int maxPoints = 0;
43 for (int j = 0; j < n; j++) {
44 maxPoints = max(maxPoints, prevRow[j]);
45 }
46
47 free(prevRow);
48 return maxPoints;
49}
50
51int main() {
52 int points[][3] = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
53 int *columnSizes;
54 int pointsSize = 3;
55
56 columnSizes = (int *)malloc(pointsSize * sizeof(int));
57 for (int i = 0; i < pointsSize; i++) {
58 columnSizes[i] = 3;
59 }
60
61 int result = maxPoints((int **)points, pointsSize, columnSizes);
62 printf("Maximum points: %d\n", result);
63
64 free(columnSizes);
65 return 0;
66}The solution uses two arrays, leftToRight and rightToLeft, to keep track of the running maximum of points at each cell considering the point loss moving horizontally. The maximum value for each cell in the current row is calculated by combining the respective running maximum from leftToRight and rightToLeft plus the points from the current cell.
This approach uses a dynamic array to store optimal points value and computes it via a prefix and suffix maximum accumulations, thereby reducing the transition complexity while still making sure every cell's deduction is feasible within two linear passes.
Time Complexity: O(m * n). Space Complexity: O(n), reducing allocation per row iteration.
1
This JavaScript approach optimizes single-row updates using a seamless combination of prefix and suffix strategies, thus making it effective in processing each cell precisely.