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.
Similar 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.
1def maxPoints(points):
2 m, n = len(points), len(points[0])
3 prevRow = points[0][:]
4
5 for i in range(1, m):
6 leftMax = [0] * n
7 rightMax = [0] * n
8
9 leftMax[0] = prevRow[0]
10 for j in range(1, n):
11 leftMax[j] = max(leftMax[j - 1] - 1, prevRow[j])
12
13 rightMax[n - 1] = prevRow[n - 1]
14 for j in range(n - 2, -1, -1):
15 rightMax[j] = max(rightMax[j + 1] - 1, prevRow[j])
16
17 for j in range(n):
18 prevRow[j] = points[i][j] + max(leftMax[j], rightMax[j])
19
20 return max(prevRow)
21
22points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]]
23print("Maximum points:", maxPoints(points))
24Utilizing Python's dynamic array handling, this method builds the processing around prefix and suffix maxima which collaborate to deduce upon beneficial transitions and maximize the points efficiently.