※ 引述《cckk3333 (皓月)》之铭言：
: ※ 引述《dementia (妖精尾巴魔导士)》之铭言：
: : 如果只讨论思考逻辑的话…
define:
N[i] = the input integer sequence with length n.
M[i] = max { N[j] * N[j+1] * ... * N[i-1] * N[i] | where j >= 0 and j <= i }
= max { M[i-1] * N[i], m[i-1] * N[i], N[i] }
m[i] = min { N[j] * N[j+1] * ... * N[i-1] * N[i] | where k >= 0 and k <= i }
= min { M[i-1] * N[i], m[i-1] * N[i], N[i] }
Max sub array product = max { M[i] | where i >= 0 and i < n }
init:
M[0] = N[0]
m[0] = N[0]
: : 0.5 检查阵列长度，如果<2，则回传错误讯息
: : 1.用”0”切阵列
: : {A,0,B} → {A} {B}
: : 2.计算每个阵列长度。如果最长=1，则回传0，结束
: : 3.将长度1的全部踢除
: : 4.如果有一个阵列长度>=4，则结果一定大于0，反之，应该蛮干就可以了。然后，如果所
: : 有的乘积都为负，则回传0，否则回传最大值，结束
: : 5. 如果有一个阵列长度>=4，则对于每个阵列做以下计算
: : 5-1 直接相乘。如果为正值，将这个值储存，否则计算5-2～5-4
: : 5-2 将阵列中第一个负数(含)前的数全踢除，如果剩余的数长度>=2，则剩余的相乘算乘
: : 积
: : 5-3 将阵列中最后一个负数(含)后的数全踢除， 如果剩余的数长度>=2，则剩余的相乘算
: : 乘积
: : 5-4 将5-2和5-3的结果储存
: : 6.将步骤5储存的所有数值取最大值，回传，结束。
: 一样只想讨论逻辑...
: 因为这篇把一些繁杂的情况考虑了 所以借用一下XD
: 只想讨论5
: 目标是scan一次
: var1, var2, var3 定义为
: var1 存scan到n时相乘最大的数 (包含最后一个)
: var2 存scan到n时相乘最小(最负)的数 (包含最后一个)
: var3 存scan到n时相乘最大的数 (不一定包含最后一个)
: 初始化
: n = 1 var1 = max(0,A[0]); (A for Array)
: var2 = min(0,A[0]);
: var3 = 够小的数
: 假设到 n 时正确 考虑 n+1
: var1 = max(var1,-var2) * ( (A[n+1] > 0) ? 1 : -1);
: var2 = max(var1,-var2) * ( (A[n+1] > 0) ? -1: 1);
: (同步)
: 接着 var3 = max(var3, var1)
: var1 = max(var1,A[n+1]);
: var2 = min(var2,A[n+1]);
: 这个主要是考虑A可能含有绝对值小于1的数(只有整数可以不用考虑)，要之后做
: 是要保证至少var3里面的答案至少是两个互乘
: 已尽量让解法类似 maximum subarray XD
: time: O(N) space: O(1)
: