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
For each row, the new optimal points using running maximum logic are computed including prefix-suffix relationships in this implementation, providing proficiency in handling large datasets within Java's environment.