Skip to content

Latest commit

 

History

History
112 lines (99 loc) · 3.35 KB

152.maximum-product-subarray.md

File metadata and controls

112 lines (99 loc) · 3.35 KB

152. Maximum Product Subarray

Dynamic Programming

Similar idea from 53. Maximum Subarray, but the difference is that the product of two negative numbers is positive. A very negative product can be very positive if multiplied by another negative later.

So we store the local maximum and minimum simultaneously during iteration. There are three ways to calculate a subarray product ending at i:

  • Fresh start at nums[i].
  • Extend previous max with nums[i]: localMax[i - 1] * nums[i].
  • Extend previous min with nums[i]: localMin[i - 1] * nums[i].
           -3,  2, -4
localMax   -3   2   * = max(-4, 2 * -4, -6 * -4) = 24
localMin   -3  -6   * = min(-4, 2 * -4, -6 * -4) = -8
globalMax  -3   2   * = max(2, 24) = 24

           -2,  3, -4
localMax   -2   3   * = max(-4, 3 * -4, -6 * -4) = 24
localMin   -2  -6   * = min(-4, 3 * -4, -6 * -4) = -12
globalMax  -2   3   * = max(3, 24) = 24
fun maxProduct(nums: IntArray): Int {
    val n = nums.size
    if (n == 0) return 0
    val localMax = IntArray(n) { Int.MIN_VALUE }
    val localMin = IntArray(n) { Int.MAX_VALUE }

    localMax[0] = nums.first()
    localMin[0] = nums.first()
    var globalMax = nums.first()
    for (i in 1 until n) {
        localMax[i] = maxOf(
            nums[i], 
            nums[i] * localMax[i - 1],
            nums[i] * localMin[i - 1]
        )
        localMin[i] = minOf(
            nums[i], 
            nums[i] * localMax[i - 1],
            nums[i] * localMin[i - 1],
        )
        globalMax = maxOf(globalMax, localMax[i])
    }
    return globalMax
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

Space Optimization

fun maxProduct(nums: IntArray): Int {
    val n = nums.size
    if (n == 0) return 0

    var previousMax = nums.first()
    var previousMin = nums.first()
    var globalMax = nums.first()
    for (i in 1 until n) {
        // We can't set `previousMax` here, see below WA.
        val currentMax = maxOf(
            nums[i], 
            nums[i] * previousMax,
            nums[i] * previousMin
        )
        val currentMin = minOf(
            nums[i], 
            nums[i] * previousMax,
            nums[i] * previousMin
        )
        globalMax = maxOf(globalMax, currentMax)
        previousMax = currentMax
        previousMin = currentMin
    }
    return globalMax
}
  • Time Complexity: O(n).
  • Space Complexity: O(1).

WA

We can't not overwrite the previousMax immediately, because we still need to use the actual previous max/min to calculate the current max/min.

fun maxProduct(nums: IntArray): Int {
    val n = nums.size
    if (n == 0) return 0

    var previousMax = nums.first()
    var previousMin = nums.first()
    var globalMax = nums.first()
    for (i in 1 until n) {
        // We overwrite the previous max immediately in this iteration.
        previousMax = maxOf(
            nums[i], 
            nums[i] * previousMax,
            nums[i] * previousMin
        )
        previousMin = minOf(
            nums[i], 
            nums[i] * previousMax, // This has been updated from above, it's not the actual previous max, which leads to WA.
            nums[i] * previousMin
        )
        globalMax = maxOf(globalMax, previousMax)
    }
    return globalMax
}
 */