int maxIncreasingCells(vector<vector<int>>& mat) { int n = mat.size(), m = mat[0].size(); unordered_map<int,vector<pair<int,int>>> mp; set<int> st; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ mp[mat[i][j]].push_back({i,j}); st.insert(-mat[i][j]); } } vector<vector<int>> val(n, vector<int>(m)); vector<int> rowPath(n), colPath(m); for(auto num : st){ num = -num; for(auto pos : mp[num]){ int r = pos.first; int c = pos.second; val[r][c] = max(rowPath[r], colPath[c]) + 1; } for(auto pos : mp[num]){ int r = pos.first; int c = pos.second; rowPath[r] = max(rowPath[r], val[r][c]); colPath[c] = max(colPath[c], val[r][c]); } } int ans = 0; for(auto len : rowPath) ans = max(len ,ans); for(auto len : colPath) ans = max(len , ans); return ans; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter