3989. Maximum Consistent Columns in a Grid

You are given a 2D integer array grid of size m x n, and an integer limit.

You may remove zero or more columns from the grid, but at least one column must remain. The relative order of the remaining columns must be preserved.

A grid is called consistent if for every row i, and for every pair of adjacent remaining columns a and b with a < b, the following holds: |grid[i][b] - grid[i][a]| <= limit.

Return the maximum number of columns that can remain such that the resulting grid is consistent.

class Solution {
public:
    int maxConsistentColumns(vector<vector<int>>& grid, int limit) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, 1);
        int res = 1;
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                bool ok = true;
                for (int r = 0; r < m; r++) {
                    if (abs(grid[r][j] - grid[r][i]) > limit) {
                        ok = false;
                        break;
                    }
                }
                if (ok) dp[j] = max(dp[j], dp[i] + 1);
            }
            res = max(res, dp[j]);
        }
        
        return res;
    }
};