C++ solution with explanation


  • 4
    Y
    class Solution {
    public:
        int maxProduct(int A[]A, int n) {
    
            // the return value, always equals
            // to the maximum product of contiguous
            // subarray of A[0:i]
            int ret = A[0];
    
            // lastmax = max{ A[j]*A[j+1]*...*A[i] }, j=0:i
            // lastmin = min{ A[j]*A[j+1]*...*A[i] }, j=0:i
            int lastmax = A[0], lastmin = A[0];
            
            // tmp variable to determine whether a
            // new ret value is available after adding A[i]
            // and help updating lastmax, lastmin
            int foo, bar; 
            for (int i = 1; i < n; i++) {
                
                // new lastmax/lastmin can only obtained by
                // the element A[i] times old lastmax/lastmin
                // or the A[i] itself alone.
                foo = A[i]*lastmax;
                bar = A[i]*lastmin;
                
                if (foo > bar) {
                    lastmax = max(foo, A[i]); 
                    lastmin = min(bar, A[i]);
                } else {
                    lastmax = max(bar,A[i]); 
                    lastmin = min(foo,A[i]);
                }
                
                if (lastmax > ret) ret = lastmax;
    
            }
            
            return ret;
        }
    };

  • 0
    J

    My Progarm is Time Limit Exceeded!
    And I can't figure it out!
    I want somebody who does well in Progarm can help me!

     class Solution {
        public:
            int maxProduct(int A[], int n) {
              if(A == NULL)
                 {
                 printf("error"); 
                 return -1;}
              if(n == 1)
                     return A[n-1];
              if(n == 2)
                     return A[n-1]*A[n-2];
              return A[n-1][n-2]>maxProduct(A,n-1)? A[n-1][n-2]:maxProduct(A,n-1);    
                    
        
            }
        };
    

  • 0
    E

    use iteration not recursion can pass the test


  • 0
    A

    Thank you for your sharing. Your code is quite succinct, but I think it is quite hard for new coders to directly come up with this algorithm. Apparently, your algorithm is a dynamic programming, but its format is not so easy to directly come up with.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.