# 152. Maximum Product Subarray

## Description

https://leetcode.com/problems/maximum-product-subarray/

Note: the input array is assumed to have at least one element.

## Solution

This is similar to the maximum subarray problem, which can be solved using Kadane's Algorithm. We can use what we learned from that problem and apply it here.

Because this question asks for the product, negative numbers have a different effect. A subarray may flip in and out of the solution as negative numbers are included.

As with the maximum sum subarray, we will keep track of the current and max product. But we will need to keep track of the minimum product too. This is because a negative product may become positive if we encounter another negative number.

### Examples

Given an input of: [5, 3, -1, 2, -2, -3, 6]

element | current product & sub array | current min product & sub array | max product & sub array |
---|---|---|---|

5 | 5 [5] | 5 [5] | 5 [5] |

3 | 15 [5,3] | 3 [3] | 15 [5,3] |

-1 | -1 [-1] | -15 [5,3,-1] | 15 [5,3] |

2 | 2 [2] | -30 [5,3,-1,2] | 15 [5,3] |

-2 | 60 [5, 3, -1, 2, -2] | -4 [2, -2] | 60 [5, 3, -1, 2, -2] |

-3 | 12 [2, -2, -3] | -180 [5, 3, -1, 2, -2, -3] | 60 [5, 3, -1, 2, -2] |

6 | 72 [2, -2, -3, -6] | -1080 [5, 3, -1, 2, -2, -3, 6] | 72 [2, -2, -3, -6] |

Given an input of [3, 2, 0, 5, 6, -1]

element | current product & sub array | current min product & sub array | max product & sub array |
---|---|---|---|

3 | 3 [3] | 3 [3] | 3 [3] |

2 | 6 [3, 2] | 2 [2] | 6 [3,2] |

0 | 0 [0] | 0 [0] | 6 [3,2] |

5 | 5 [5] | 0 [0, 5] | 6 [3,2] |

6 | 30 [5,6] | 0 [0, 5, 6] | 30 [5,6] |

-1 | 0 [0, 5, 6, -1] | -30 [5, 6, -1] | 30 [5, 6] |

Last updated