Online Judge Solutions

Sunday, November 2, 2014

Maximum Product Subarray

 
Solution 1:

int maxProduct(int A[], int n) {
         int max=A[0], min = A[0], ans = A[0];
        
         for(int i = 1; i < n; i++) {
             int mx = max, mn = min;
             max = std::max(A[i], std::max(mx*A[i], mn*A[i]));
             min = std::min(A[i], std::min(mx*A[i], mn*A[i]));
            
             ans = std::max(ans, max);
         }
        
         return ans;
}

Solution 2:

 int maxProduct(int A[], int n) {
         int max = A[0];
         int maxPos = 1.0;
         int minNeg = 1.0;
        
         for(int i = 0; i < n; i++) {
             if (A[i] > 0) {
                 maxPos *= A[i];
                
                 minNeg = min(1, minNeg*A[i]);
                   
                 max = std::max(max,maxPos);
             }
             else if (A[i] < 0) {
                 int tmp = maxPos * A[i];
                
                 if (minNeg < 0) {
                    maxPos = std::max(1, minNeg * A[i]);
                    max = std::max(max,maxPos);
                 }
                 else
                    maxPos = 1;
                 minNeg = tmp;
             }
             else {
                 maxPos = 1.0;
                 minNeg = 1.0;
                
                 max = std::max(0, max);
             }
         }
        
         return max;
    }


No comments:

Post a Comment