Share the First C++ Solution with Notes


  • 6
    R

    This question is pretty different from Maximum Sum of Subarray. The reason is that a negative value in array will revolute the previous maximum product to the minimum and vice versa. So both temporary results should be kept.

    class Solution {
    public:
        int maxProduct(int A[], int n) {
            if (n==1) return A[0];
            
            int max_temp=0,min_temp=0,result=std::numeric_limits<int>::min();
            
            for (int i=0;i<n;i++){
                if (A[i]>0){
                    max_temp=max(max_temp*A[i],A[i]);//Assign the Temporary Maximum Product
                    min_temp=min_temp*A[i];
                }
                else if (A[i]==0){
                    max_temp=0;
                    min_temp=0;
                }
                else{//Negative value, **maximum** and **minimum** products will be  revoluted. 
                    int temp=max_temp;
                    max_temp=min_temp*A[i];
                    min_temp=min(temp*A[i],A[i]);//Assign the Temporary Minimum Product
                }
                result=max(max_temp,result);
            }
            return result;
        }
    };

  • 11
    Z
    class Solution {
    public:
        int maxProduct(int A[],  int n) {
            if (n < 1) return 0;
            int r = A[0];
            int max_p = A[0];
            // max_p is the maximum product that could be achieved
            // from the subarrays ending at the current position.
            int min_p = A[0]; 
            // The minimum product that could be achieved from 
            // the subarrays ending at the current position.
            for(int i=1; i<n; i++){
                // The maximum or minimum product of the subarrays 
                // ending at the current position could be achieved from the next three values.
                int a = max_p*A[i];
                // the max product of subarray ending at the previous position multiply the current value
                int b = min_p*A[i];
                // the minimum product of subarray ending at the previous position multiply the current value
                int c = A[i];
                // the current value
                max_p = max(max(a,  b),  c);
                min_p = min(min(a,  b),  c);
                if (max_p > r) r = max_p;
            }
            return r;
        }
    };
    

    Same idea. But it looks simpler.


  • 0
    S

    I don't think yours is better. At least your variables need to have some meaning, instead of using 'a', 'b', etc.


  • 0
    Z

    I have added some comments to make the code easier to understand. Thanks.


  • 0
    S

    Thank you for improving that code. It becomes much more readable!


  • 0
    H

    i think you should consider the number between 0 and 1. If the array is 2, 3, 0.00001, 4, 5. the maxProduct is 45 = 20, but your solution is 2 * 3 0.00001 * 4 * 5 < 20


  • 0
    B

    array is int array :)


  • 0
    H

    oh, sorry :)


  • 0
    K

    Yeah. Checked it. It's correct. Nice!


  • 0
    Z
    This post is deleted!

  • 0
    K

    Yes. It's correct. Just figured it out that "max_p = max(max(a, b), c);" updated to the most current contiguous subarray once a zero is encountered. Nice!


Log in to reply
 

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