产品最大子阵 [英] Maximum Product Subarray

问题描述

我有n个正实数的数组

和我必须找出最大的产品子阵这个给定的数组。

And I have to find out the Maximum Product Subarray for this given array.

如何实现DP解决方案的问题？

How to implement DP Solution for the problem ?

解释溶液的DP制剂

推荐答案

由于对最大的和的解决方案众所周知，您可以

Since the solution for maximal sum is known, you can

• 计算登录每个阵列的项目到另一个数组
• 已知的算法应用到新阵列
• EXP 的结果就是答案。

• compute log of each array's item into another array
• apply the known algorithm to the new array
• exp of the result is the answer.

（但你可以平凡调整现有算法，这已经是@ nevets的答复中提到，更换常数0（这是加中性元素）1。）

(But you can just trivially adjust the existing algorithm, which is already mentioned in @nevets's answer. Replace the constant 0 (which is additive neutral element) with 1.)

这篇关于产品最大子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！