Easy Java Solution || Dynamic Programing || Top Down || Bottom Up
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {

    static int dp[][][];

    static int findMaxProfitTopDown(int arr[][], int i, int j, int power){
        int n = arr.length;
        int m = arr[0].length;
        if(i>=n || j>=m) return Integer.MIN_VALUE;
        if(i==n-1 && j==m-1){
            if(power>0 && arr[i][j]<0) return 0;
            else return arr[i][j];
        }

        if(dp[i][j][power]!=Integer.MIN_VALUE) return dp[i][j][power];

    
        int a = findMaxProfitTopDown(arr,i+1,j,power);
        int b = findMaxProfitTopDown(arr,i,j+1,power);

        int take = arr[i][j]+Math.max(a,b);
        int notTake = -(int)1e9;
        if(power>0 && arr[i][j]<0){
            int c = findMaxProfitTopDown(arr,i+1,j,power-1);
            int d = findMaxProfitTopDown(arr,i,j+1,power-1);
            notTake = Math.max(c,d);
        }
        return dp[i][j][power] = Math.max(take,notTake);
    }


    static int findMaxProfitBottomUp(int arr[][]){
        int n = arr.length;
        int m = arr[0].length;
        int dp[][][] = new int[n+1][m+1][3];

        

        for (int p = 0; p < 3; p++) {
            dp[n-1][m-1][p] = (p > 0 && arr[n-1][m-1] < 0) ? 0 : arr[n-1][m-1];
        }

        for(int p=0; p<3; p++){
            for(int i=0; i<n+1; i++){
                dp[i][m][p] = Integer.MIN_VALUE;
            }
        }

        for(int p=0; p<3; p++){
            for(int j=0; j<m+1; j++){
                dp[n][j][p] = Integer.MIN_VALUE;
            }
        }
        
       
        for(int i=n-1; i>=0; i--){
            for(int j=m-1; j>=0; j--){
                for(int power=0; power<3; power++){
                    if (i == n - 1 && j == m - 1) continue; // Skip 
                    int a = dp[i+1][j][power];
                    int b = dp[i][j+1][power];

                    int take = arr[i][j]+Math.max(a,b);
                    int notTake = -(int)1e9;
                    if(power>0 && arr[i][j]<0){
                        int c = dp[i+1][j][power-1];
                        int d = dp[i][j+1][power-1];
                        notTake = Math.max(c,d);
                    }
                    dp[i][j][power] = Math.max(take,notTake);
                }
            }
        }
        return dp[0][0][2];
    }
    public int maximumAmount(int[][] coins) {
        int n = coins.length;
        int m = coins[0].length;
        dp = new int[n+1][m+1][4];
        for(var a : dp) for(var b : a) Arrays.fill(b,Integer.MIN_VALUE);
        return findMaxProfitBottomUp(coins);
    }
}
```
['Java']