Lintcode: Maximum Product Subarray

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

Have you met this question in a real interview? 

Yes

Example

For example, given the array [2,3,-2,4], the contiguous subarray[2,3] has the largest product = 6.

Tags Expand 

Dynamic Programming Subarray

Compared to maximum subarray problem, the sum could be reset to 0 when sum is negative, but product cannot.

Naive solution:
Get all products start from each element
Many repetitive calculations.
Time: O(n*n)
Space: O(1)
cannot pass -- time limit

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: /** * @param nums: a vector of integers * @return: an integer */ int maxProduct(vector<int>& nums) { // write your code here if(nums.size() == 0) return 0; int res = INT_MIN; for(int start = 0; start < nums.size(); start++){ int prod = 1; for(int i = start; i < nums.size(); i++){ prod *= nums[i]; res = max(res, prod); } } return res; } };

DP solution:
thought and code: http://blog.csdn.net/worldwindjp/article/details/39826823
Time: O(n)
Space: O(1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: /** * @param nums: a vector of integers * @return: an integer */ int maxProduct(vector<int>& nums) { if(nums.size() == 0) return 0; int res = INT_MIN; int max_pos = 1; int max_neg = 1; for(int i = 0; i < nums.size(); i++){ int x = max_pos * nums[i]; int y = max_neg * nums[i]; max_pos = max(max(x, y), nums[i]); max_neg = min(min(x, y), nums[i]); res = max(res, max_pos); } return res; } };