【LeetCode】152、乘积最大子数组

【LeetCode】152、乘积最大子数组

一、dp

1.1 dp

从前向后遍历, 当遍历到 nums[i] 时, 有如下三种情况 能得到最大值:

1. 只使用 nums[i], 例如 [0.1, 0.3, 0.2, 100] 则 [100] 是最大值
2. 使用 max(nums[0…i-1]) * nums[i], 例如 [1, 3, 2, 100], 则 [1, 3, 2, 100] 是最大值, 因为 nums[0…i-1] 的 [1, 3, 2] 是最大值
3. 使用 min(nums[0…i-1]) * nums[i], 例如 [-1, 3, -2, -100], 则 [-1, 3, -2, -100] 是最大值, 因为 nums[0…i-1] 的 [-1, 3, -2] 是最小值, 最小值乘以最小值得到最大值

所以, 每一步, 都取上述三种情况的最小值和最大值. 逐步向后递推.

// go
func maxProduct(nums []int) int {
    ans := nums[0]
    mi, ma := nums[0], nums[0] // 初始值
    var curmin, curmax int // 临时值, 提前申请, 避免重复申请
    for i := 1; i < len(nums); i++ {
        v := nums[i]
        curmin = min(v, min(ma*v, mi*v))
        curmax = max(v, max(ma*v, mi*v))
        mi, ma = curmin, curmax
        ans = max(ans, ma)
    }
    return ans
}

算法讲解071【必备】子数组最大累加和问题与扩展-下

参考
关于「无后效性」

• 某个阶段的状态一旦确定了，那么此后的过程不再受之前曾经的状态和决策的影响
• 不管你过去经历过什么状态，做过什么决策，未来和过去无关
• 当前的状态是此前历史的一个综合给出的结果，历史影响你也只是造就了你当前的状态，通过当前状态去影响你未来的进程

1.2 简化代码

为了简化代码, 可以不从1开始遍历
通过设置 mi, ma 为 1, 1, 即可从0开始遍历了
参考

func maxProduct(nums []int) int {
    ans := nums[0]
    mi, ma := 1, 1
    var curmi, curma int
    for _, v := range nums {
        curmi = min(v, mi*v, ma*v)
        curma = max(v, mi*v, ma*v)
        mi, ma = curmi, curma
        ans = max(ans, ma)
    }
    return ans
}

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = nums[0];
        int mi = 1, ma = 1;
        for (int v : nums) {
            int curmi = min({v, v*mi, v*ma});
            int curma = max({v, v*mi, v*ma});
            mi = curmi;
            ma = curma; // 注意 c++ mi, ma = curmi, curma 有问题
            /*
            `mi, ma = curmi, curma;` 在 C++ 中是有问题的。这是因为 C++ 不支持这种同时赋值的语法。C++ 中的逗号运算符不会像 Python 或 Golang 那样实现多重赋值；相反，它会依次执行每个表达式，并返回最后一个表达式的值。因此，`mi, ma = curmi, curma;` 实际上只会对 `ma` 进行赋值，而不是同时对 `mi` 和 `ma` 赋值。
            */
            ans = max(ans, ma);
        }
        return ans;
    }
};

// go 同上

# python
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = nums[0]
        mi, ma = 1, 1
        for v in nums:
            curmi = min(v, v*mi, v*ma)
            curma = max(v, v*mi, v*ma)
            mi, ma = curmi, curma
            ans = max(ans, ma)
        return ans

// rust
impl Solution {
    pub fn max_product(nums: Vec<i32>) -> i32 {
        let mut ans = nums[0];
        let mut mi = 1;
        let mut ma = 1;
        for v in nums {
            let curmi = v.min(v*mi).min(v*ma);
            let curma = v.max(v*mi).max(v*ma);
            mi = curmi;
            ma = curma;
            ans = ans.max(ma);
        }
        ans
    }
}

// js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let ans = nums[0];
    let mi = 1;
    let ma = 1;
    for (const v of nums) {
        let curmi = Math.min(v, v*mi, v*ma);
        let curma = Math.max(v, v*mi, v*ma);
        mi = curmi;
        ma = curma;
        ans = Math.max(ans, ma);
    }
    return ans;
};

// ts