LEETCODE WEEKLY 432 | Q-2
IntuitionThe problem requires us to maximize the amount we can collect while traversing a grid. We are allowed to move either right or down at each step, and we
# Intuition
The problem requires us to maximize the amount we can collect while traversing a grid. We are allowed to move either right or down at each step, and we can only ignore a limited number of negative values during the traversal. We will need a dynamic programming (DP) approach to track the maximum sum at each cell, while also managing the number of negative values that can be skipped.

# Approach
1. **Grid Setup**: We have a grid where each cell contains either a positive or negative value. We need to keep track of the maximum sum we can accumulate while traversing the grid, considering that we are allowed to skip at most two negative values.
2. **DP Initialization**: 
   - Initialize a 3D DP array `dp[i][j][k]` where `i` and `j` are the row and column indices of the grid, and `k` represents how many negative values have been skipped (0, 1, or 2).
   - For the starting cell, if the value is negative, initialize `dp[0][0][0]` to the value of the cell and `dp[0][0][1]` to 0.
3. **DP Transition**:
   - For each cell `(i, j)` and each possible number of skipped negative values (`k`), propagate the value to the neighboring cells `(i+1, j)` and `(i, j+1)`.
   - If the value in the neighboring cell is negative and we haven't skipped two negatives yet, allow skipping it and transition to `dp[ni][nj][k+1]`.
4. **Final Answer**: After filling the DP table, the final answer will be the maximum value among the three possibilities in the bottom-right cell: `dp[m-1][n-1][0]`, `dp[m-1][n-1][1]`, and `dp[m-1][n-1][2]`.

# Complexity
- Time complexity: \(O(m * n * 3)\), where `m` and `n` are the number of rows and columns of the grid, and the factor of 3 comes from the three possible states of negative values that can be skipped.
- Space complexity: \(O(m * n * 3)\), due to the 3D DP table that stores the results for each state.

# Code
```cpp
class Solution {
public:
    int maximumAmount(vector<vector<int>>& coins) {

        int m = coins.size();
        int n = coins[0].size();
        int dp[505][505][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = INT_MIN;
                }
            }
        }

        if (coins[0][0] >= 0) {
            dp[0][0][0] = coins[0][0];
        } else {
            dp[0][0][0] = coins[0][0];
            dp[0][0][1] = 0; 
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    if (dp[i][j][k] == INT_MIN)
                        continue;
                    for (auto& it : vector<pair<int, int>>{{1, 0}, {0, 1}}) {
                        int ni = i + it.first, nj = j + it.second;
                        if (ni >= m || nj >= n)
                            continue;
                        int val = dp[i][j][k];
                        int c = coins[ni][nj];
                        dp[ni][nj][k] = max(dp[ni][nj][k], val + c);
                        if (c < 0 && k < 2) {
                            dp[ni][nj][k + 1] = max(dp[ni][nj][k + 1], val);
                        }
                    }
                }
            }
        }

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

        return ans;
    }
};

['C++']