Weekly Contest Problem 2 using DP
Complexity
Time complexity:
O(M * N * 3)
Space complexity:
O(M * N * 3)Code
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(M * N * 3)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(M * N * 3)
# Code
```java []
class Solution {
    public int maximumAmount(int[][] coins) {
        
        int r=coins.length,c=coins[0].length;

        int[][][] dp=new int[r][c][3];

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                Arrays.fill(dp[i][j],Integer.MIN_VALUE);
            }
        }
        if(coins[0][0]<0){
            Arrays.fill(dp[0][0],0);
            dp[0][0][0]=coins[0][0];
        }
        else{
            Arrays.fill(dp[0][0],coins[0][0]);
        }

        for(int i=0;i<coins.length;i++){
            for(int j=0;j<coins[0].length;j++){
                if(i!=0 || j!=0){
                for(int k=0;k<3;k++){
                    int MAX=Integer.MIN_VALUE;

                    if(i-1>=0){
                        MAX=Math.max(dp[i-1][j][k],MAX);
                    }
                    if(j-1>=0){
                        MAX=Math.max(dp[i][j-1][k],MAX);
                    }
                    if(coins[i][j]<0){
                        if(k==0){
                            dp[i][j][0]=Math.max(MAX+coins[i][j],dp[i][j][0]);
                            dp[i][j][1]=Math.max(MAX,dp[i][j][1]);
                        }
                        else if(k==1){
                            dp[i][j][1]=Math.max(MAX+coins[i][j],dp[i][j][1]);
                            dp[i][j][2]=Math.max(MAX,dp[i][j][2]);
                        }
                        else{
                            dp[i][j][2]=Math.max(dp[i][j][2],MAX+coins[i][j]);
                        }
                    }
                    else{
                        dp[i][j][k]=Math.max(dp[i][j][k],MAX+coins[i][j]);
                    }
                }
                }
            }
        }
        return Math.max(Math.max(dp[r-1][c-1][0],dp[r-1][c-1][1]),dp[r-1][c-1][2]);
    }
}
```
['Dynamic Programming', 'Greedy', 'Java']