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.
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6int maxPoints(vector<vector<int>>& points) {
7 int m = points.size();
8 int n = points[0].size();
9
10 vector<int> prevRow(n);
11
12 for (int j = 0; j < n; ++j) {
13 prevRow[j] = points[0][j];
14 }
15
16 for (int i = 1; i < m; ++i) {
17 vector<int> leftToRight(n), rightToLeft(n), currentRow(n);
18
19 leftToRight[0] = prevRow[0];
20 for (int j = 1; j < n; ++j) {
21 leftToRight[j] = max(leftToRight[j - 1] - 1, prevRow[j]);
22 }
23
24 rightToLeft[n - 1] = prevRow[n - 1];
25 for (int j = n - 2; j >= 0; --j) {
26 rightToLeft[j] = max(rightToLeft[j + 1] - 1, prevRow[j]);
27 }
28
29 for (int j = 0; j < n; ++j) {
30 currentRow[j] = points[i][j] + max(leftToRight[j], rightToLeft[j]);
31 }
32
33 prevRow = currentRow;
34 }
35
36 return *max_element(prevRow.begin(), prevRow.end());
37}
38
39int main() {
40 vector<vector<int>> points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
41 int result = maxPoints(points);
42 printf("Maximum points: %d\n", result);
43 return 0;
44}In this C++ solution, vectors leftToRight and rightToLeft are used similar to the C solution, to calculate the maximum points possible moving through each row. The current row maximum is updated using these running totals.
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.