LeetCode-in-All

152. Maximum Product Subarray

Medium

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]

Output: 0

Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

Solution

object Solution {
    def maxProduct(arr: Array[Int]): Int = {
        var ans = Int.MinValue
        var cprod = 1

        for (j <- arr) {
            cprod = cprod * j
            ans = math.max(ans, cprod)
            if (cprod == 0) {
                cprod = 1
            }
        }

        cprod = 1

        for (i <- arr.length - 1 to 0 by -1) {
            cprod = cprod * arr(i)
            ans = math.max(ans, cprod)
            if (cprod == 0) {
                cprod = 1
            }
        }

        ans
    }
}