写文章只是为了整理思路吗，在远古的学生时代，可能只是为了机试参加个比赛什么的， 作为一届老人，早已没了会点啥就想拿出来炫耀的年纪， 会点除了能混过面试，是不是也能和面试官聊出点感情，程序似乎无可避免悄然而然成了我们生活中心 ，相顾两无言，唯把代码谈。

朦胧周末早上起床，昨晚与老友聊此题记忆犹新。 今日把递推式子写一下，发现昨晚睡意之下并非完全想的清楚。

拿到这个问题，长的都像动态规划，你可能很快就兴奋的想到一个二维动态规划的式子 ，

p (I , j)  = p (i-1, j)  * e（i）

p 是 product （乘积）， e 是数组元素 element（i）

O(n^2) 的 算法已经诞生。快速实现一运行，TL （时间超限,这是行业黑话，意思是你这个傻x，有O（n）算法)
人生就是如此艰难，承认自己菜是不是很难。

我们来想一维动态规划算法.
我们只需要求出以 e(i) 结尾的最大乘积，其中i= 1，...,n 那么最终结果就是：

result = max (pmax(0), pmax(1),  pmax(2), … , pmax(n))  

那么如何求 pmax（i） , 即以 e（i） 结尾的连续最大乘积 ？ 不得不说 ，e(i) 必须是最后一个因子，使得问题简化了。
继续想，e（I） 乘以什么会最大。分两种情况讨论

1. e(i) ≥ 0 , 期望乘以一个大正数，即期望pmax（i-1）是个最大非负数。可是pmax(i-1) 最大就是个负数怎么办, 那不指望了，e(i) 本身就是最大值。所以
   pmax(i) = max (pmax(i-1) * e(i) , e(i)) .
2. e(i) < 0 , 期望乘以一个最小负数（这样绝对值大）， 负负得正， 如果连负数都没有, 那也不指望了， e (i),本身就挺大，不要乘了。 但是这最小负数乘积去哪里找呢。 最小负数可能出现在最小连续乘积 。 当前只要保存这个值就好了, 写完下面的式子我们再求 pmin (i) .
   pmax(i) = max (pmin(i-1) * e(i) , e(i))

继续出发，如何求 pmin(i), 同样的思路， 若以e(i) 结尾的连续最小乘积？

1. e(i) ≥ 0， 期望乘以一个最小负数，这个肯定包含在最小值里面， 要是连负数都没有，就别乘了，e(i)本身就最小。所以
   pmin(i) = min(pmin(i-1 ) * e(i), e(i))
2. e(i) < 0 , 期望乘以一个最大非负数，这个肯定包含在最大值里面，要是连非负数也没有，同理就别乘了。所以
   pmin = min (pmax(i-1) * e(i), e(i))

为了清晰一些不妨将以上表达式写为

pmax (i) =  max (  pmax(i-1)  *  e(i) ,  pmin (i-1) * e(i), e(i)),
pmin (i) =  min  (  pmin (i-1) * e(i) , pmax.(i-1) * e(i), e(i)).   

最后

result = max (pmax(0), pmax(1),  pmax(2), … , pmax(n))

博客

最大连续子乘积

原文：https://www.cnblogs.com/xiaozhi007/p/13661137.html