Pretty straightforward Java solution.


  • 1

    The only negative number we should NOT include is the leftmost one or the rightmost one, and skip those zeros in the way, and we can easily get the answer.

    public class Solution {
        public int maxProduct(int[] nums) {
            int n = nums.length;
            int maxPro = Math.max(nums[0], nums[n - 1]);
            int[] dp = new int[n];
            
            // left to right
            dp[0] = nums[0];
            for (int i = 1; i < n; i++) {
                if (nums[i - 1] == 0) dp[i] = nums[i];
                else dp[i] = nums[i] * dp[i - 1];
                maxPro = Math.max(maxPro, dp[i]);
            }
            
            // right to left
            dp[n - 1] = nums[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                if (nums[i + 1] == 0) dp[i] = nums[i];
                else dp[i] = nums[i] * dp[i + 1];
                maxPro = Math.max(maxPro, dp[i]);
            }
            return maxPro;
        }
    }
    

Log in to reply
 

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