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.
1function maxPoints(points) {
2 const m = points.length;
3 const n = points[0].length;
4
5 let prevRow = [...points[0]];
6
7 for (let i = 1; i < m; i++) {
8 let leftToRight = [...prevRow];
9 for (let j = 1; j < n; j++) {
10 leftToRight[j] = Math.max(leftToRight[j], leftToRight[j - 1] - 1);
11 }
12
13 let rightToLeft = [...prevRow];
14 for (let j = n - 2; j >= 0; j--) {
15 rightToLeft[j] = Math.max(rightToLeft[j], rightToLeft[j + 1] - 1);
16 }
17
18 for (let j = 0; j < n; j++) {
19 leftToRight[j] = points[i][j] + Math.max(leftToRight[j], rightToLeft[j]);
20 }
21
22 prevRow = leftToRight;
23 }
24
25 return Math.max(...prevRow);
26}
27
28const points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]];
29console.log('Maximum points:', maxPoints(points));
30JavaScript offers a dynamic method to iterate and maximize profits using strategies akin to its C-based counterparts while leveraging the language's powerful array manipulation capabilities.
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
public class Solution {
public static int MaxPoints(int[][] points) {
int m = points.Length;
int n = points[0].Length;
int[] prevRow = new int[n];
Array.Copy(points[0], prevRow, n);
for (int i = 1; i < m; i++) {
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftMax[j] = Math.Max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightMax[j] = Math.Max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
prevRow[j] = points[i][j] + Math.Max(leftMax[j], rightMax[j]);
}
}
int maxPoints = 0;
foreach (var val in prevRow) {
if (val > maxPoints) maxPoints = val;
}
return maxPoints;
}
public static void Main() {
int[][] points = new int[][] {
new int[] {1, 2, 3},
new int[] {1, 5, 1},
new int[] {3, 1, 1}
};
Console.WriteLine("Maximum points: " + MaxPoints(points));
}
}
In this C# solution, careful attention is given to maintaining efficiency and state during transitions by deriving the potential from each end with optimal in-place adjustments.