<p>You are given an <code>m x n</code> integer matrix <code>points</code> (<strong>0-indexed</strong>). Starting with <code>0</code> points, you want to <strong>maximize</strong> the number of points you can get from the matrix.</p>

<p>To gain points, you must pick one cell in <strong>each row</strong>. Picking the cell at coordinates <code>(r, c)</code> will <strong>add</strong> <code>points[r][c]</code> to your score.</p>

<p>However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows <code>r</code> and <code>r + 1</code> (where <code>0 &lt;= r &lt; m - 1</code>), picking cells at coordinates <code>(r, c<sub>1</sub>)</code> and <code>(r + 1, c<sub>2</sub>)</code> will <strong>subtract</strong> <code>abs(c<sub>1</sub> - c<sub>2</sub>)</code> from your score.</p>

<p>Return <em>the <strong>maximum</strong> number of points you can achieve</em>.</p>

<p><code>abs(x)</code> is defined as:</p>

<ul>
	<li><code>x</code> for <code>x &gt;= 0</code>.</li>
	<li><code>-x</code> for <code>x &lt; 0</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong><strong> </strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-40-26-diagram-drawio-diagrams-net.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> points = [[1,2,3],[1,5,1],[3,1,1]]
<strong>Output:</strong> 9
<strong>Explanation:</strong>
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/12/screenshot-2021-07-12-at-13-42-14-diagram-drawio-diagrams-net.png" style="width: 200px; height: 299px;" />
<pre>
<strong>Input:</strong> points = [[1,5],[2,3],[4,2]]
<strong>Output:</strong> 11
<strong>Explanation:</strong>
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == points.length</code></li>
	<li><code>n == points[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= points[r][c] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        # Keep previous row
        prev = points[0]
        curr = [0]*n

        for i in range(1, m):
            # At some cell[i][j], there will be penalties to any previous row cell that is to the left or right
            # Keep a running variable to get max from top or left/right penalties
            running = 0
            
            # Get left penalties
            for j in range(n):
                running = max(running - 1, prev[j])
                curr[j] = running

            # Get right penalties
            for j in range(n-1, -1, -1):
                running = max(running - 1, prev[j])
                curr[j] = max(curr[j], running) + points[i][j]

            prev = curr

        return max(prev)
"""
input: m x n matrix points
output: int maximum points achieved

At some points[i][j], add to aggregate point sum points[i][j] - abs(j - [j - 1])

[1,2,3],
     ^
[1,5,1],
   ^
[3,1,1]
     ^
ans = 3 + 4 + 2

[1,1,1,1,1,1,1,1,1,5]
[10,1,1,1,1,1,1,1,1,1]

# O(mn^2)

[-1,0,1,0,-1,-2,-3,-4,-5,-6,-6] # O(n)

[10,1,1,1,1,1,1,1,1,1]
 ^
[11,2,2, ... ]
Only need to keep track of the previous row
Don't know which from previous row will yield highest points
Keep array for previous rows aggregate sum of points'
For each row we get the largest points and add to current column

Reduce time it takes to calculate aggregate sum + penalties of previous row
At some cell[i][j], there will be penalties to any previous row cell that is to the left or right
Use 2 different auxillary arrays: one for penalties from the left and one for penalties from the right
Choose max between both arrays for a given index

# O(mn) time

[1,2,3],
[1,5,1], *
[3,1,1]

[1,1,1]
[1,2,3]

[1,5,1]

[2,7,4]
"""
1506