Skip to main content

Maximum Non Negative Product in a Matrix

算是个简单的DP, 扫一遍就行,用滚动数组可以优化空间复杂度到On,这里比较粗暴。On^2&On^2

impl Solution {    pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {        use std::cmp::max;                let mut posi: Vec<Vec<i64>> = vec![vec![-1;grid[0].len()];grid.len()];        let mut nega: Vec<Vec<i64>> = posi.clone();        if grid[0][0] >= 0 {            posi[0][0] = grid[0][0] as i64;        } else {            nega[0][0] = -grid[0][0] as i64;        }        for i in 1..grid.len() {            if grid[i][0] >= 0 {                posi[i][0] = get_mul(posi[i-1][0], grid[i][0]);                nega[i][0] = get_mul(nega[i-1][0], grid[i][0]);            } else {                nega[i][0] = get_mul(posi[i-1][0], -grid[i][0]);                posi[i][0] = get_mul(nega[i-1][0], -grid[i][0]);            }        }        for i in 1..grid[0].len() {            if grid[0][i] >= 0 {                posi[0][i] = get_mul(posi[0][i-1], grid[0][i]);                nega[0][i] = get_mul(nega[0][i-1], grid[0][i]);            } else {                nega[0][i] = get_mul(posi[0][i-1], -grid[0][i]);                posi[0][i] = get_mul(nega[0][i-1], -grid[0][i]);            }        }        for i in 1..grid.len() {            for j in 1..grid[0].len() {                if grid[i][j] >= 0 {                    posi[i][j] = get_mul(max(posi[i-1][j], posi[i][j-1]), grid[i][j]);                    nega[i][j] = get_mul(max(nega[i-1][j], nega[i][j-1]), grid[i][j]);                } else {                    nega[i][j] = get_mul(max(posi[i-1][j], posi[i][j-1]), -grid[i][j]);                    posi[i][j] = get_mul(max(nega[i-1][j], nega[i][j-1]), -grid[i][j]);                }            }        }
        let res = posi[grid.len()-1][grid[0].len()-1] % 1000000007;        if res < 0 {            for i in 0..grid.len() {                for j in 0..grid[0].len() {                    if grid[i][j] == 0 {                        return 0;                    }                }            }        }        res as i32    }}
fn get_mul(x: i64, y: i32) -> i64 {    if x == -1 {        -1    } else {        x * y as i64    }}