3418. Maximum Amount of Money Robot Can Earn

/**
 * Problem: LeetCode 3418 - Maximum Amount of Money Robot Can Earn
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

class Solution {
    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int NEG_INF = -1_000_000_000;

        // dp[i][j][k]: max profit at cell (i, j) with k neutralizations used (k in {0, 1, 2})
        int[][][] dp = new int[m][n][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], NEG_INF);
            }
        }

        // Base case at (0, 0)
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0][0][1] = 0;
            dp[0][0][2] = 0;
        } else {
            dp[0][0][1] = coins[0][0];
            dp[0][0][2] = coins[0][0];
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                for (int k = 0; k < 3; k++) {
                    int maxVal = NEG_INF;

                    // Transition from cell above (i - 1, j)
                    if (i > 0) {
                        if (dp[i - 1][j][k] != NEG_INF) {
                            maxVal = Math.max(maxVal, dp[i - 1][j][k] + coins[i][j]);
                        }
                        if (k > 0 && coins[i][j] < 0 && dp[i - 1][j][k - 1] != NEG_INF) {
                            maxVal = Math.max(maxVal, dp[i - 1][j][k - 1]);
                        }
                    }

                    // Transition from cell to the left (i, j - 1)
                    if (j > 0) {
                        if (dp[i][j - 1][k] != NEG_INF) {
                            maxVal = Math.max(maxVal, dp[i][j - 1][k] + coins[i][j]);
                        }
                        if (k > 0 && coins[i][j] < 0 && dp[i][j - 1][k - 1] != NEG_INF) {
                            maxVal = Math.max(maxVal, dp[i][j - 1][k - 1]);
                        }
                    }

                    dp[i][j][k] = maxVal;
                }
            }
        }

        return Math.max(dp[m - 1][n - 1][0], Math.max(dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]));
    }
}

"""
Problem: LeetCode 3418 - Maximum Amount of Money Robot Can Earn
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        m, n = len(coins), len(coins[0])
        NEG_INF = -10**9

        # dp[i][j][k]: max profit reaching (i, j) with k neutralizations used (k in {0, 1, 2})
        dp = [[[NEG_INF] * 3 for _ in range(n)] for _ in range(m)]

        # Base case at (0, 0)
        dp[0][0][0] = coins[0][0]
        if coins[0][0] < 0:
            dp[0][0][1] = 0
            dp[0][0][2] = 0
        else:
            dp[0][0][1] = coins[0][0]
            dp[0][0][2] = coins[0][0]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue

                for k in range(3):
                    max_val = NEG_INF

                    # From top (i - 1, j)
                    if i > 0:
                        if dp[i - 1][j][k] != NEG_INF:
                            max_val = max(max_val, dp[i - 1][j][k] + coins[i][j])
                        if k > 0 and coins[i][j] < 0 and dp[i - 1][j][k - 1] != NEG_INF:
                            max_val = max(max_val, dp[i - 1][j][k - 1])

                    # From left (i, j - 1)
                    if j > 0:
                        if dp[i][j - 1][k] != NEG_INF:
                            max_val = max(max_val, dp[i][j - 1][k] + coins[i][j])
                        if k > 0 and coins[i][j] < 0 and dp[i][j - 1][k - 1] != NEG_INF:
                            max_val = max(max_val, dp[i][j - 1][k - 1])

                    dp[i][j][k] = max_val

        return max(dp[m - 1][n - 1])

/**
 * Problem: LeetCode 3418 - Maximum Amount of Money Robot Can Earn
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {
        int m = coins.size();
        int n = coins[0].size();
        const int NEG_INF = -1e9;

        // dp[i][j][k]: max profit reaching (i, j) with k neutralizations used (k in {0, 1, 2})
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(3, NEG_INF)));

        // Base case at (0, 0)
        dp[0][0][0] = coins[0][0];
        if (coins[0][0] < 0) {
            dp[0][0][1] = 0;
            dp[0][0][2] = 0;
        } else {
            dp[0][0][1] = coins[0][0];
            dp[0][0][2] = coins[0][0];
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                for (int k = 0; k < 3; k++) {
                    int maxVal = NEG_INF;

                    // From top (i - 1, j)
                    if (i > 0) {
                        if (dp[i - 1][j][k] != NEG_INF) {
                            maxVal = max(maxVal, dp[i - 1][j][k] + coins[i][j]);
                        }
                        if (k > 0 && coins[i][j] < 0 && dp[i - 1][j][k - 1] != NEG_INF) {
                            maxVal = max(maxVal, dp[i - 1][j][k - 1]);
                        }
                    }

                    // From left (i, j - 1)
                    if (j > 0) {
                        if (dp[i][j - 1][k] != NEG_INF) {
                            maxVal = max(maxVal, dp[i][j - 1][k] + coins[i][j]);
                        }
                        if (k > 0 && coins[i][j] < 0 && dp[i][j - 1][k - 1] != NEG_INF) {
                            maxVal = max(maxVal, dp[i][j - 1][k - 1]);
                        }
                    }

                    dp[i][j][k] = maxVal;
                }
            }
        }

        return max({dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});
    }
};

/**
 * Problem: LeetCode 3418 - Maximum Amount of Money Robot Can Earn
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} coins
 * @return {number}
 */
var maximumAmount = function(coins) {
    const m = coins.length;
    const n = coins[0].length;
    const NEG_INF = -1e9;

    // dp[i][j][k]: max profit reaching (i, j) with k neutralizations used (k in {0, 1, 2})
    const dp = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => [NEG_INF, NEG_INF, NEG_INF])
    );

    // Base case at (0, 0)
    dp[0][0][0] = coins[0][0];
    if (coins[0][0] < 0) {
        dp[0][0][1] = 0;
        dp[0][0][2] = 0;
    } else {
        dp[0][0][1] = coins[0][0];
        dp[0][0][2] = coins[0][0];
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) continue;

            for (let k = 0; k < 3; k++) {
                let maxVal = NEG_INF;

                // From top (i - 1, j)
                if (i > 0) {
                    if (dp[i - 1][j][k] !== NEG_INF) {
                        maxVal = Math.max(maxVal, dp[i - 1][j][k] + coins[i][j]);
                    }
                    if (k > 0 && coins[i][j] < 0 && dp[i - 1][j][k - 1] !== NEG_INF) {
                        maxVal = Math.max(maxVal, dp[i - 1][j][k - 1]);
                    }
                }

                // From left (i, j - 1)
                if (j > 0) {
                    if (dp[i][j - 1][k] !== NEG_INF) {
                        maxVal = Math.max(maxVal, dp[i][j - 1][k] + coins[i][j]);
                    }
                    if (k > 0 && coins[i][j] < 0 && dp[i][j - 1][k - 1] !== NEG_INF) {
                        maxVal = Math.max(maxVal, dp[i][j - 1][k - 1]);
                    }
                }

                dp[i][j][k] = maxVal;
            }
        }
    }

    return Math.max(dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]);
};