LeetCode Challenge: Maximum Product Subarray
The most naive approach is iterating over all the ranges of the array, and iterate elements in the range to compute a product for this range, the time complexity will be $O(N^3)$.
An optimization is using a
table to store the computed result,
table[i][j] means the product of range(i, j), so when we compute the result of range(i, j+1), we just need to compute the value of
table[i][j] * arr[j+1] => table[i][j+1].
But the overall time complexity is still: $O(N^2)$, it will be Time Limit Exceeded.
Approach of linear scan
Similar with previous challenge of maximum subarray. The difference is we need to save both current minimum and maximum product, because if current element is less then zero, minimum maybe also a negative value, the product of them maybe the next maximum.
The time complexity is: $O(N)$.
Preparing for an interview? Check out this!