【回溯篇】在Python中实现数组中查找具有最大乘积的相邻子数组
Python之刃
Python基础知识 | Python实战例子 | 算法 | Python数据分析 | Python爬虫精选 | Python高手技巧
Official Account
"""
在数组中查找具有最大乘积的相邻子数组（至少包含一个数字）。
例如，给定数组[2,3,-2,4]，相邻子数组[2,3]的最大乘积为6。
"""
from functools import reduce
def max_product(nums):
"""
:type nums: List[int]
:rtype: int
"""
lmin = lmax = gmax = nums[0]
for i in range(len(nums)):
t1 = nums[i] * lmax
t2 = nums[i] * lmin
lmax = max(max(t1, t2), nums[i])
lmin = min(min(t1, t2), nums[i])
gmax = max(gmax, lmax)
'''
另一种方法是打印最大乘积和子数组
例如:
subarray_with_max_product([2,3,6,-1,-1,9,5])
#=> max_product_so_far: 45, [-1, -1, 9, 5]
subarray_with_max_product([-2,-3,6,0,-7,-5])
#=> max_product_so_far: 36, [-2, -3, 6]
subarray_with_max_product([-4,-3,-2,-1])
#=> max_product_so_far: 24, [-4, -3, -2, -1]
subarray_with_max_product([-3,0,1])
#=> max_product_so_far: 1, [1]
'''
def subarray_with_max_product(arr):
''' arr是正数/负数的列表 '''
l = len(arr)
product_so_far = max_product_end = 1
max_start_i = 0
so_far_start_i = so_far_end_i = 0
all_negative_flag = True
for i in range(l):
max_product_end *= arr[i]
if arr[i] > 0:
all_negative_flag = False
if max_product_end <= 0:
max_product_end = arr[i]
max_start_i = i
if product_so_far <= max_product_end:
product_so_far = max_product_end
so_far_end_i = i
so_far_start_i = max_start_i
if all_negative_flag:
print("max_product_so_far: %s, %s" %
(reduce(lambda x, y: x * y, arr), arr))
else:
print("max_product_so_far: %s, %s" %
(product_so_far, arr[so_far_start_i:so_far_end_i + 1]))
注：小编已将文中代码整理成了Jupyter Notebook的形式方便大家在线运行！
领取方式