Sharing my Java solution: 1ms


  • 2
    public int maxProduct(int[] nums) {
            int max = nums[0];
            int cache = 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0){
                    cache = 1;
                    max = Math.max(max, 0);
                } else {
                    cache *= nums[i];
                    max = Math.max(max, cache);
                }
            }
            cache = 1;
            for (int i = nums.length - 1; i > 0; i--) {
                if (nums[i] == 0){
                    cache = 1;
                    max = Math.max(max, 0);
                } else {
                    cache *= nums[i];
                    max = Math.max(max, cache);
                }
            }
            return  max;
        }
    

  • 1
    G

    Ported to C++ and added some document comments

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            // The first element will always be the greatest to-beat
            int maxRun = nums[0];
            
            /**
             * Look through forward.
             * In general, if the longest run is bookended by negative
             * numbers, then it won't matter which direction we approach it
             * from, since the negatives will cancel.
             * 
             * However, if there is only one negative (either in front of
             * or behind) the longest run, it will matter which direction
             * we approach it from.
             * 
             * If we consider the negative first, the entire run will be
             * negative, then we will miss the product we are looking for.
             * 
             * However, if we consider the negative last, the entire run
             * will be positive until that negative, which is what we wanted
             * to find.
             * 
             * Thankfully, on a number line, there are only two directions
             * from which to approach this product summation, hence it is
             * computationally feasible to simply consider the same
             * list of numbers twice.
             */
            int tmp = 1;
            for (int num: nums) {
                if (num == 0) {
                    /**
                     * Handle the first non-zero number we encounter after
                     * the zero, if any, in the else{} below
                     */
                    tmp = 1;
                    // Note that maxRun could be negative, hence 0 greater
                    maxRun = max(maxRun, 0);
                }
                else {
                    /**
                     * Note that, as we encounter negative numbers, tmp
                     * will become negative, but it will become positive
                     * again if it encounters another negative number,
                     * so there's no need to reset; just keep a running
                     * product tally.
                     */
                    tmp *= num;
                    maxRun = max(maxRun, tmp);
                }
            }
            
            // Look through backward (see extended comment above)
            tmp = 1;
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums[i] == 0) {
                    /**
                     * Handle the first non-zero number we encounter after
                     * the zero, if any, in the else{} below
                     */
                    tmp = 1;
                    // Note that maxRun could be negative, hence 0 greater
                    maxRun = max(maxRun, 0);
                }
                else {
                    /**
                     * Note that, as we encounter negative numbers, tmp
                     * will become negative, but it will become positive
                     * again if it encounters another negative number,
                     * so there's no need to reset; just keep a running
                     * product tally.
                     */
                    tmp *= nums[i];
                    maxRun = max(maxRun, tmp);
                }
            }
            return maxRun;
        }
    };
    

Log in to reply
 

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