Minimal Approach using DFS | Beats 💯
Intuition
Each step try to move right and down and keep the max returned value.

We can use recursion to achieve this.
Then we can use dp to optimize it.


We a
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- Each step try to move right and down and keep the max returned value.
  - We can use recursion to achieve this.
  - Then we can use dp to optimize it.
- We also need to take care of negative values 2 times
  - For this we can use variable $$k=2$$ to check how many times a negative value has been eliminated.
  - If we encounter a -ve value
    - We can choose to include it or exclude it while reducing k by 1 (only if k>0) 
    - and then return the max of two approaches.
-   Since we are using 3 variables 1. for row, 2. for column and 3. k
    - We will need a 3D DP to optimize.  

# Code
```java []
class Solution {
    public int maximumAmount(int[][] coins) {
        int m=coins.length;
        int n=coins[0].length;
        Integer[][][] dp=new Integer[m][n][3];
        
        return calc(coins,0,0,2,dp);
    }

    private int calc(int[][] coins,int i,int j,int k,Integer[][][] dp) {
        int m=coins.length;
        int n=coins[0].length;

        if(i>=m||j>=n) {
            return -(int)1e9;
        }
        if(i==m-1&&j==n-1) 
            return coins[i][j]>=0?coins[i][j]:(k>0?0:coins[i][j]);
    
        if(dp[i][j][k]!=null) 
            return dp[i][j][k];
        
        int d=coins[i][j]+calc(coins,i+1,j,k,dp);
        if(coins[i][j]<0&&k>0) 
            d=Math.max(d,calc(coins,i+1,j,k-1,dp));
        
        int r=coins[i][j]+calc(coins,i,j+1,k,dp);
        if(coins[i][j]<0&&k>0) 
            r=Math.max(r,calc(coins,i,j+1,k-1,dp));
        return dp[i][j][k]=Math.max(d,r);
    }
}
```
['Dynamic Programming', 'Depth-First Search', 'Java']