011动态规划解决最大连续乘积子数组.md

动态规划解决最大连续乘积子数组

动态规划介绍

这是承接之前002动态规划的章节，继续使用动态规划解决实际问题。

问题描述

最大连续乘积子数组问题，表示求一个数组的子数组，保证子数组的乘积最大。

与最大子数组和最大不同的是，乘积需要考虑正负，因此动态规划时需要把正负数的最大值都保存下来。

动态规划的设计思路是这样的，虽然背包问题也用动态规划会把中间结果保存到数组，但连续子字符串因为是连续的只需要保留最后的结果即可，通过一个for循环一直扫到尾，记录max和min，还有全局的一个result。

如何使用动态规划

首先第一步还是定义函数和变量，然后给一个测试用例准备。

def max_multiple_substring(a):
  # a for array data
  result = a[0]
  max = a[0]
  min = a[0]

a = [-2.5, 4, 0, 3, 0.5, 8, -1]
max_multiple_substring(a)

然后可以写for循环，主要是判断max、min还有最后的result，唯一的算法就是要么是乘以后面的要么是新的。

def max_multiple_substring(a):
  # a for array data
  result = a[0]
  currentMax = a[0]
  currentMin = a[0]

  for i in range(1, len(a)):
    currentMax = max(currentMax * a[i], currentMin * a[i], a[i])
    currentMin = min(currentMax * a[i], currentMin * a[i], a[i])
    result = max(currentMax, currentMin, result)

  return result

a = [-2.5, 4, 0, 3, 0.5, 8, -1]
max_multiple_substring(a)
# Print 12

这是本章内容，希望对你有所帮助。进入下一章