# The Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array `[2,3,-2,4]`

,

the contiguous subarray `[2,3]`

has the largest product = `6`

.

# Notes:

- Keep track of a minAt and a maxAt of product ending with each index. The trick is to record minAt, it covers the case that previously has a negative number (we discarded in maxAt), but later have another negative number which together may result in a bigger product.
- minAt and maxAt should be updated after all computed, so use a temp variable to hold first.

# Java Solution

public class Solution { public int maxProduct(int[] A) { int maxAt = A[0]; int minAt = A[0]; int max = A[0]; int tempMax, tempMin; for(int i = 1; i < A.length; i++){ tempMax = Math.max(Math.max(maxAt * A[i], minAt * A[i]), A[i]); tempMin = Math.min(Math.min(maxAt * A[i], minAt * A[i]), A[i]); maxAt = tempMax; minAt = tempMin; max = Math.max(maxAt, max); } return max; } }

Advertisements