152.maximum-product-subarray.md

152. Maximum Product Subarray

Dynamic Programming

Similar idea from 53. Maximum Subarray, but we store the local maximum and minimum simultaneously since the local minimum * next negative number might be the next maximum. (For example, [-2, 3, -4], it will be 3 if we transit the local max only, however, the answer is 24)

           -3,  2, -4
localMax   -3   2   * = max(-4, 2 * -4, -6 * -4)
localMin   -3  -6   * = min(-4, 2 * -4, -6 * -4)
globalMax  -3   2

fun maxProduct(nums: IntArray): Int {
    // The local max / min when considering the current number
    val localMax = IntArray(nums.size)
    val localMin = IntArray(nums.size)
    var globalMax = nums[0]
    localMax[0] = nums[0]
    localMin[0] = nums[0]
    for (i in 1 until nums.size) {
        val current = nums[i]
        localMax[i] = maxOf(
            current,
            maxOf(localMax[i - 1] * current, localMin[i - 1] * current)
        )
        localMin[i] = minOf(
            current,
            minOf(localMax[i - 1] * current, localMin[i - 1] * current)
        )
        globalMax = max(localMax[i], globalMax)
    }
    return globalMax
}

Space Optimization

fun maxProduct(nums: IntArray): Int {
    if (nums.size == 1) return nums[0]
    var globalMax = nums[0]
    var maxProduct = nums[0]
    var minProduct = nums[0]
    for (i in 1 until nums.size) {
        val current = nums[i]
        val currentMaxProduct = maxProduct * current
        val currentMinProduct = minProduct * current

        maxProduct = max(
            current,
            max(currentMaxProduct, currentMinProduct)
        )
        minProduct = min(
            current,
            min(currentMaxProduct, currentMinProduct)
        )
        globalMax = max(globalMax, maxProduct)
    }
    return globalMax
}