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.
1import java.util.*;
2
3public class MaxPoints {
4 public static int maxPoints(int[][] points) {
5 int m = points.length;
6 int n = points[0].length;
7
8 int[] prevRow = new int[n];
9 System.arraycopy(points[0], 0, prevRow, 0, n);
10
11 for (int i = 1; i < m; i++) {
12 int[] leftToRight = new int[n];
13 int[] rightToLeft = new int[n];
14 int[] currentRow = new int[n];
15
16 leftToRight[0] = prevRow[0];
17 for (int j = 1; j < n; j++) {
18 leftToRight[j] = Math.max(leftToRight[j - 1] - 1, prevRow[j]);
19 }
20
21 rightToLeft[n - 1] = prevRow[n - 1];
22 for (int j = n - 2; j >= 0; j--) {
23 rightToLeft[j] = Math.max(rightToLeft[j + 1] - 1, prevRow[j]);
24 }
25
26 for (int j = 0; j < n; j++) {
27 currentRow[j] = points[i][j] + Math.max(leftToRight[j], rightToLeft[j]);
28 }
29
30 prevRow = currentRow;
31 }
32
33 return Arrays.stream(prevRow).max().getAsInt();
34 }
35
36 public static void main(String[] args) {
37 int[][] points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
38 System.out.println("Maximum points: " + maxPoints(points));
39 }
40}
41Using three arrays, this Java solution calculates the max points with linear iterations over each row where transitions between rows are handled by comparing values in leftToRight and rightToLeft.
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.