力扣1594. 矩阵的最大非负积

力扣1594. 矩阵的最大非负积

题目

题目解析及思路

题目要求返回从左上到右下的最大非负积，本题和简单图dp的区别就是出现了负数

若grid[i][j] >= 0则和简单图dp一致，dp[i][j] = max(dp[i-1][j],dp[i][j-1]) * grid[i][j]

若grid[i][j] < 0则分两种情况，由于不知道该留大的还是小的，于是开两个dp数组把大小两个都存下来

即mn[i][j] = max(mx[i-1][j],mx[i][j-1]) * grid[i][j];

mx[i][j] = min(mn[i-1][j],mn[i][j-1]) * grid[i][j];

代码

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int mod = 1e9 + 7;
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<long long>> mx(n,vector<long long>(m));
        vector<vector<long long>> mn(n,vector<long long>(m));
        //初始化起点
        mx[0][0] = mn[0][0] = grid[0][0];
        //第一行第一列只从一个方向更新，预处理一下
        for(int i=1;i<n;i++){
            mx[i][0] = mn[i][0] = mx[i-1][0] * grid[i][0];
        }
        for(int i=1;i<m;i++){
            mx[0][i] = mn[0][i] = mx[0][i-1] * grid[0][i];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(grid[i][j] >= 0){
                    //正数就正常更新
                    mx[i][j] = max(mx[i-1][j],mx[i][j-1]) * grid[i][j];
                    mn[i][j] = min(mn[i-1][j],mn[i][j-1]) * grid[i][j];
                }
                else{
                    //负数就用max求较小值
                    mn[i][j] = max(mx[i-1][j],mx[i][j-1]) * grid[i][j];
                    mx[i][j] = min(mn[i-1][j],mn[i][j-1]) * grid[i][j];
                }
            }
        }
        return mx[n-1][m-1] >= 0 ? mx[n-1][m-1] % mod : -1;
    }
};