A naive but straigtforward solution


  • 7
    L

    When encounter a 0, split the sequence and get the max of the left, right, and 0.
    If the accumulative result is negative, check two cases: 1. divide out the elements from left till the first
    negative element. 2. divide out the elements from right till the first negative element. Return the max result.

    int helper(int A[], int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        
        if (l == r) {
            return A[l];
        }
        
        int max_prod = INT_MIN;
        int acc = 1;
        for (int i = l; i <= r; ++i) {
            if (A[i] == 0) {
                return max(helper(A, l, i - 1), max(0, helper(A, i + 1, r)));
            }
            acc *= A[i];
            max_prod = max(max_prod, acc);
        }
        
        // find first negtive number from left and divide out elements before it (including itself).
        if (acc < 0) {
            for (int i = l; i <= r; ++i) {
                acc /= A[i];
                if (A[i] < 0) {
                    break;
                }
            }
        }
        
        return max(max_prod, acc);
    }
    
    int maxProduct(int A[], int n) {
        return helper(A, 0, n - 1);
    }

  • 0
    W

    Nice Code, with O(n) space in worst case.


  • 0
    L

    Neat.
    But is there some code missing? I can't see the "divide out the elements from right till the first negative element" part.


  • 0
    L

    This case is already covered by the first loop.


Log in to reply
 

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