#### Let's start with recursive definition of maximum product subarray

Given an array A[1..n].

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

- The
**MPS in A[i..n] starting at A[i]**(This is the case when A[i] is included.) - 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

**A[i]**(MPS in A[i..n] ending at A[i]⁆)- 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

**A[i]**(MPS in A[i..n] ending at A[i]⁆)- 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
```