数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究用 Python 查找连续子数组的最大乘积
假设我们有一个名为 nums 的数组，我们必须找到其中一个数组内的连续子数组（至少包含一个数字）的元素的乘积，其乘积最大。因此，如果数组是 [1,9,2,0,2,5]，输出将是 18，因为连续子数组 [1,9,2] 的乘积最大。
为了解决这个问题，我们将遵循以下步骤 -
- max_list := 大小为 nums 的列表，用 0 填充
- min_list := 大小为 nums 的列表，用 0 填充
- min_list := 大小为 nums 的列表，用 0 填充
- 对于 i 在 1 到 nums 长度之间的范围
- max_list[i] = max_list[i - 1]*nums[i]、min_list[i - 1]*nums[i] 和 nums[i] 中的最大值
- min_list[i] = minof min_list[i - 1]*nums[i]、nums[i]、max_list[i - 1]*nums[i]
- 返回 max_list 的最大值
让我们看看下面的实现以获得更好的理解 -
示例
class Solution(object): def maxProduct(self, nums): max_list = [0] * len(nums) min_list = [0] * len(nums) max_list[0] = nums[0] min_list[0] = nums[0] for i in range(1,len(nums)): max_list[i] = max(max(max_list[i-1]*nums[i],min_list[i-1]*nums[i]),nums[i]) min_list[i] = min(min(min_list[i-1]*nums[i],nums[i]),max_list[i-1]*nums[i]) return max(max_list) ob1 = Solution() print(ob1.maxProduct([1,9,2,0,2,5]))
输入
[1,9,2,0,2,5]
输出
18
更新日期:2020 年 10 月 20 日
超过 1K 的浏览量
广告