Monday, May 11, 2015

152 Maximum Product Subarray

来源:Leetcode

原帖:https://oj.leetcode.com/problems/maximum-product-subarray/

题目:
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.

代码:
 class Solution {  
 public:  
   int maxProduct(int A[], int n) {  
     int result = A[0];  
     int maximum = A[0], minimum = A[0];  
     int curMax = A[0], curMin = A[0];  
     for (int i = 1; i < n; ++i) {  
       curMax = max({A[i], A[i] * maximum, A[i] * minimum});  
       curMin = min({A[i], A[i] * maximum, A[i] * minimum});  
       maximum = curMax;  
       minimum = curMin;  
       result = max(result, maximum);  
     }  
     return result;  
   }  
 };  


No comments:

Post a Comment