3148. Maximum Difference Score in a Grid

You are given an m x n matrix grid consisting of positive integers. You can move from a cell in the matrix to any other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with the value c1 to a cell with the value c2 is c2 - c1.

You can start at any cell, and you have to make at least one move.

Return the maximum total score you can achieve.

class Solution {
public:
    int maxScore(vector<vector<int>>& A) {
        vector<int> dp(A[0].size(), -1e6);
        int res = INT_MIN;
        bool fl = false;
        for(int i = A.size() - 1; i >= 0; i--) {
            for(int j = A[0].size() - 1; j >= 0; j--) {
                if(j + 1 < A[0].size()) dp[j] = max(dp[j], dp[j+1]);
                if(fl) res = max(res, dp[j] - A[i][j]);
                fl = true;
                dp[j] = max(dp[j], A[i][j]);
            }
        }
        return res;
    }
};