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.
1def maxPoints(points):
2 m, n = len(points), len(points[0])
3 prevRow = points[0][:]
4
5 for i in range(1, m):
6 leftToRight = prevRow[:]
7 for j in range(1, n):
8 leftToRight[j] = max(leftToRight[j], leftToRight[j - 1] - 1)
9
10 rightToLeft = prevRow[:]
11 for j in range(n - 2, -1, -1):
12 rightToLeft[j] = max(rightToLeft[j], rightToLeft[j + 1] - 1)
13
14 for j in range(n):
15 leftToRight[j] = points[i][j] + max(leftToRight[j], rightToLeft[j])
16
17 prevRow = leftToRight
18
19 return max(prevRow)
20
21points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]]
22print("Maximum points:", maxPoints(points))
23Similar to the C-based implementations, this Python approach optimally determines maximum points by storing pre-computed row values. The leftToRight and rightToLeft adjustments ensure correct score after factoring in distance deductions.
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#include <algorithm>
using namespace std;
int maxPoints(vector<vector<int>>& points) {
int m = points.size();
int n = points[0].size();
vector<int> prevRow(points[0].begin(), points[0].end());
for (int i = 1; i < m; ++i) {
vector<int> leftMax(n);
vector<int> rightMax(n);
vector<int> currentRow(n);
leftMax[0] = prevRow[0];
for (int j = 1; j < n; ++j) {
leftMax[j] = max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; --j) {
rightMax[j] = max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; ++j) {
currentRow[j] = points[i][j] + max(leftMax[j], rightMax[j]);
}
prevRow = currentRow;
}
return *max_element(prevRow.begin(), prevRow.end());
}
int main() {
vector<vector<int>> points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
int result = maxPoints(points);
printf("Maximum points: %d\n", result);
return 0;
}The primary aim in this C++ code is to optimize the array management and expedite the element-wise summation for determining ideal points. By using dynamic arrays, computation resources are conserved and enhanced.