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

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

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 r and r + 1 (where 0 &lt;= r &lt; m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:


	x for x &gt;= 0.
	-x for x &lt; 0.


&nbsp;
Example 1: 

Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9
Explanation:
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.


Example 2:

Input: points = [[1,5],[2,3],[4,2]]
Output: 11
Explanation:
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.


&nbsp;
Constraints:


	m == points.length
	n == points[r].length
	1 &lt;= m, n &lt;= 105
	1 &lt;= m * n &lt;= 105
	0 &lt;= points[r][c] &lt;= 105


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        
        for i in range(m - 1):
            for j in range(1, n):
                points[i][j] = max(points[i][j], points[i][j - 1] - 1)
            
            for j in range(n - 2, -1, -1):
                points[i][j] = max(points[i][j], points[i][j + 1] - 1)
            
            for j in range(n):
                points[i + 1][j] += points[i][j]
        
        return max(points[m - 1])
/* 
   -> take a frame same width as points,this frame will contains most effective(which provide maximum sum)values which will later get 
	added to next values from next row.

   -> conditions to update values in frame 
		* we will keep only those values which will contribute maximum in next row addition

	e.g-->
		points --->[[1,2,3]
					[1,5,1]
					[3,1,1]]

		for 1st iteration frame <--- [1,2,3] rest of two loops will not affect frame so in 
		2nd itreration frame <--------[2,7,4] <-------- [1,2,3] + [1,5,1]
		now we have to update frame so it can give max values for next row addition
		 0 1 2   
		[2,7,4] 
		  \ 
		[2,7,4]  check left to right--> just check value at index 0 can contribute more than curr_sum at index 1 but to do so it has to give up (1-0) a penalty,here 7 can contribute more than 2-1=1 in next sum.
		2 7 4        now check for index 2,where (7-1)>4
		   \
		2 7 6
					now do in reverse,can 6 contribute more than 7 no ( 7 >(6-1) )  
					can 7 contibute more than 2 yes (2<(7-1)),so now  frame will be
		6 7 6       now we can cal optimal-frame for rest of the matrix.
	+   3 1 1
 ------------------- 
		9 8 7  check left to right--> can 9 can contibute 8>(9-1) no; can 8 can contibute for index 2 no simlier for right to left
*/

class Solution {
	public long maxPoints(int[][] points) {
		long[] frame = new long[points[0].length];

		for (int i = 0; i < points.length; i++) {
			for (int j = 0; j <frame.length; j ++) frame[j] += points[i][j];

			for (int j = 1; j < frame.length; j ++) frame[j] = Math.max(frame[j], frame[j - 1] - 1);

			for (int j=frame.length-2;j>=0;j--) frame[j] = Math.max(frame[j], frame[j + 1] - 1);

			for(long k:frame) System.out.println(k);
		}


		long ans = 0;
		for (int i = 0; i < frame.length; i ++) {
			ans = Math.max(ans, frame[i]);
		}
		return ans;
	}
}
class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        vector<vector<long long>> dp(points.size(), vector<long long>(points[0].size(), -1));
        
        for (int i = 0; i < points[0].size(); ++i) {
            dp[0][i] = points[0][i];
        }
        
        for (int i = 1; i < points.size(); ++i) {
            for (int j = 0; j < points[i].size(); ++j) {
                for (int k = 0; k < points[i].size(); ++k) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] - abs(k - j) + points[i][j]);
                }
            }
        }
        
        long long max_ans = -1;
        for (const auto v : dp.back()) {
            max_ans = max(max_ans, v);
        }
        
        return max_ans;
    }
};
var maxPoints = function(points) {
    let prev = points[0];
    let curr = Array(points[0].length);

    for(let i = 1; i<points.length; i++){

        // from left to right;
        for(let j = 0, maxAdd=0; j<points[0].length;j++){
            maxAdd = Math.max(maxAdd-1, prev[j]);
            curr[j] = points[i][j] + maxAdd;
        }

        for(let j = points[0].length-1, maxAdd = 0; j>=0; j--){
            maxAdd = Math.max(maxAdd-1, prev[j]);
            curr[j] = Math.max(curr[j], points[i][j] + maxAdd)
        }

        prev = curr;
        curr = Array(points[0].length)

    }
    return Math.max(...prev)
};
Maximum Number of Points with Cost