# Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return *the product*.

```
class Solution {
public int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = max; // store the max because before updating min your max will already be updated
max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
if (max > ans) {
ans = max;
}
}
return ans;
}
}
```

## Related Problems

Given a string s, partition s such that every substring of the partition is a palindrome.

Return *the ***minimum*** cuts needed for a palindrome partitioning of* s.

Given an integer array nums, return *the length of the longest ***strictly increasing subsequence**.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.