洛阳作公司网站,做h5的网站页面,网站怎么建设教程,金融网站建设内容【LeetCode】152、乘积最大子数组 文章目录 一、dp1.1 dp1.2 简化代码 二、多语言解法 一、dp
1.1 dp
从前向后遍历, 当遍历到 nums[i] 时, 有如下三种情况 能得到最大值:
只使用 nums[i], 例如 [0.1, 0.3, 0.2, 100] 则 [100] 是最大值使用 max(nums[0…i-1]) * nums[i], 例…【LeetCode】152、乘积最大子数组 文章目录 一、dp1.1 dp1.2 简化代码 二、多语言解法 一、dp
1.1 dp
从前向后遍历, 当遍历到 nums[i] 时, 有如下三种情况 能得到最大值:
只使用 nums[i], 例如 [0.1, 0.3, 0.2, 100] 则 [100] 是最大值使用 max(nums[0…i-1]) * nums[i], 例如 [1, 3, 2, 100], 则 [1, 3, 2, 100] 是最大值, 因为 nums[0…i-1] 的 [1, 3, 2] 是最大值使用 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
}二、多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp
class Solution {
public:int maxProduct(vectorint 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: Veci32) - 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
