```    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;
}```
```//This was my Solution
long long findMaxSubsetSum(int N, vector<int> &A) {
// code here
pair<long long,long long> prev, curr;
if(N == 1)
return A[0];
prev = {A[N-1] , 0};
for(int i = N - 2; i >= 0 ; i--){
curr.first = max(A[i]+ prev.first, A[i] + prev.second);
curr.second = prev.first;
prev = curr;
}
return max(curr.first, curr.second);

}
//This is others solution
// recursive -> O(2^n)
long long recursive_approach(vector<int>&arr,int index,int n){
if(index>=n){
return 0;
}

long long take,notTake;

take=arr[index]+recursive_approach(arr,index+1,n);
notTake=(index+1>=n?0:arr[index+1]+ recursive_approach(arr,index+2,n));

return max(take,notTake);
}
//memoized -> O(n), Space->O(n)
long long memoization_approach(vector<int>&arr,int index,int n,vector<int>&t){
if(index>=n){
return 0;
}

long long take,notTake;

if(t[index]!=-1){
return t[index];
}

take=arr[index]+memoization_approach(arr,index+1,n,t);
notTake=(index+1>=n?0:arr[index+1]+ memoization_approach(arr,index+2,n,t));

return t[index]=max(take,notTake);
}
//tabulation -> O(n), O(n)
long long tabulation_approach(vector<int>&arr,int n){
vector<int>t(n+2,0);
long long take,notTake;
for(int i=n-1;i>=0;i--){
take=arr[i]+t[i+1];
notTake=(i+1>=n?0:arr[i+1]+t[i+2]);
t[i]=max(take,notTake);
}
return t[0];
}
//optimal -> O(n) , O(1)
long long spaceOptimized_approach(vector<int>&arr,int n){
long long take,notTake,prev_1,prev_2;
prev_1=0;
prev_2=0;

for(int i=n-1;i>=0;i--){
take=arr[i]+prev_1;
notTake=(i+1>=n?0:arr[i+1]+prev_2);
prev_2=prev_1;
prev_1=max(take,notTake);
}

return prev_1;
}```
star

Sun May 28 2023 11:06:04 GMT+0000 (Coordinated Universal Time) https://leetcode.com/contest/weekly-contest-347/problems/maximum-strictly-increasing-cells-in-a-matrix/

#c++ #dynammic_programming
star

Sun May 14 2023 17:31:18 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/e047b92794316450814b29de56cc9c6ec18371b7/1

#dynammic_programming #dp #maximum_subset_sum