Medium — Dynamic Programming | Array | Kadane’s Algorithm

The Problem

Find the contiguous subarray within an array of integers that has the largest product and return that product.

Approach

Use dynamic programming to track both maximum and minimum products at each position, swapping them when encountering negative numbers. This handles the case where negative numbers can turn a small product into a large one.

Time: O(n) · Space: O(1)

Code

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Initialize variables to keep track of the maximum and minimum product ending at the current position.
        max_product = min_product = result = nums[0]

        # Iterate through the array starting from the second element.
        for i in range(1, len(nums)):
            # If the current element is negative, swap max_product and min_product
            # because multiplying a negative number can turn the maximum into the minimum.
            if nums[i] < 0:
                max_product, min_product = min_product, max_product

            # Update max_product and min_product based on the current element.
            max_product = max(nums[i], max_product * nums[i])
            min_product = min(nums[i], min_product * nums[i])

            # Update the overall result with the maximum product found so far.
            result = max(result, max_product)

        return result

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment