Proof of O(1) space, O(n) running time solution

Given an array A[1..n].

The MPS (maximum product subarray) in A[i..n] is the maximum of

1. The MPS in A[i..n] starting at A[i] (This is the case when A[i] is included.)
2. The MPS in A[i+1..n](This is the case when A[i] excluded.)

The second case can be solved recursively. We need to define the slightly different subproblem MPS in A[i..n] starting at A[i] in the first case.

The MPS in A[i..n] starting at A[i] is the maximum of

1. A[i] (MPS in A[i..n] ending at A[i]⁆)
2. the maximum of A[i]×(MPS in A[i+1..n] starting at A[i+1]) and A[i]×(MinPS in A[i+1..n] starting at A[i+1]) (Not ending at A[i])

MinPS means minimum product subarray. The second case is correct because A[i] x (any product of subarray) lies within A[i] x MPS and A[i] x MinPS. We can define MinPS in A[i+1..n] starting at A[i+1] similarly as follows.

The MinPS in A[i..n] starting at A[i] is the minimum of

1. A[i] (MPS in A[i..n] ending at A[i]⁆)
2. the minimum of A[i]×(MPS in A[i+1..n] starting at A[i+1]) and A[i]×(MinPS in A[i+1..n] starting at A[i+1]) (Not ending at A[i])

Let
MPS(i) denotes MPS in A[i..n],
MPSsi(i) denotes MPS in A[i..n] starting at A[i],
and MinPSsi(i) denotes MinPS in A[i..n] starting at A[i].
The recursive algorithm is as follows.

``````MPS(i)
if i==n
return A[n]
else
return max⁡(MPS(i+1), MPSsi(i))
MPSsi(i)
if i==n
return A[n]
else
return max⁡(A[i], max(A[i]×MinPSsi(i+1), A[i]×MPSsi(i+1))

MinPSsi(i)
if i==n
return A[n]
else
return min(A[i], min(A[i]×MinPSsi(i+1), A[i]×MPSsi(i+1))
``````

Although this recursive algorithm is slow, we can turn it into a dynamic programming easily. Since MPS(i) only depends on MPS(i+1),** MPSsi(i+1)**, and MinPSsi(i+1). We only need to a space of 3 variables and n steps to compute the answer MPS(1). Here is the final dynamic programming solution.

``````MPSdynamic(A[1..n])
MPS = MPSsi = MinPSsi = A[n]
for i=n−1 down to 1
tmp = MPSsi
MPSsi = max(A[i], max(A[i]×MPSsi, A[i]×MinPSsi)
MinPSsi = min(A[i], min(A[i]×tmp, A[i]×MinPSsi)
MPS=max⁡(MPS, MPSsi)
return MPS
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.