[C++] Beats 100% runtime single dimension DP array
IntuitionVerify that going from a cell 1 to 5 to 9 is the same as going from a cell 1 to 9:
5 - 1 + 9 - 5 = 9 - 1Therefore we only need to find the maximum diff
# Intuition
Verify that going from a cell 1 to 5 to 9 is the same as going from a cell 1 to 9:
5 - 1 + 9 - 5 = 9 - 1

Therefore we only need to find the maximum difference between any cell and a cell to the bottom or right of it.

# Approach
We can use an array maximum with size of cols to keep track of the maximum element to the bottom or right for the row below the one currently being processed.

If we update the array right to left, part of the array will be updated to the current row and we can read from it to get the maximum value for the cell on the right of the one being processed.

# Complexity
- Time complexity:
O(rows * cols)

- Space complexity:
O(cols)

# Code
```cpp []
class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), result = INT_MIN;
        vector<int> maximum(cols);
        maximum[cols - 1] = grid[rows - 1][cols - 1];
        for (int x = cols - 2; x >= 0; --x) {
            result = max(result, maximum[x + 1] - grid[rows - 1][x]);
            maximum[x] = max(grid[rows - 1][x], maximum[x + 1]);
        }
        for (int y = rows - 2; y >= 0; --y) {
            result = max(result, maximum[cols - 1] - grid[y][cols - 1]);
            maximum[cols - 1] = max(grid[y][cols - 1], maximum[cols - 1]);
            for (int x = cols - 2; x >= 0; --x) {
                maximum[x] = max(maximum[x], maximum[x + 1]);
                result = max(result, maximum[x] - grid[y][x]);
                maximum[x] = max(maximum[x], grid[y][x]);
            }
        }
        return result;
    }
};
```

Feel free to ask questions if you like my solution!
['C++']