关键词搜索优化_北京王府井攻略_软文推广发稿平台_广告行业怎么找客户

力扣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;}
};