【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, curmaxans = 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, 1var curmi, curma intfor _, v := range nums {curmi = min(v, mi*v, ma*v)curma = max(v, mi*v, ma*v)mi, ma = curmi, curmaans = 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, 1for v in nums:curmi = min(v, v*mi, v*ma)curma = max(v, v*mi, v*ma)mi, ma = curmi, curmaans = 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