maximum_product_subarray

View Source

 1# @leet start
 2class Solution:
 3    def maxProduct(self, nums: list[int]) -> int:
 4        """
 5        This problem asks us to return the maximum subarray product of an array.
 6        This requires us to keep track of the minimum result and the maximum
 7        result we've seen so far, since any number is present in the array.
 8
 9        There are three cases:
10        1. A positive number is strictly beneficial.
11        2. A negative number could be beneficial or not.
12        3. A zero always resets your progress.
13
14        So, we can encode these three cases in keeping track of the min and
15        max so far. Either number has 3 parts:
16
17        1. We want to use curr, cause if the minimum and maximum are very small,
18        it's better to just restart.
19        2. Max * curr, because multiplying max by a large negative number or a large
20        positive number can create either a large positive or small negative number.
21        3. Min * curr, for the same reason.
22
23        At the end we return the max_so_far product we've seen.
24        """
25        if not nums:
26            return 0
27
28        result, max_so_far, min_so_far = nums[0], nums[0], nums[0]
29
30        for curr in nums[1:]:
31            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
32            min_so_far = min(curr, max_so_far * curr, min_so_far * curr)
33            max_so_far = temp_max
34
35            result = max(max_so_far, result)
36
37        return result
38
39
40# @leet end
41
42
43def test():
44    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def maxProduct(self, nums: list[int]) -> int:
 5        """
 6        This problem asks us to return the maximum subarray product of an array.
 7        This requires us to keep track of the minimum result and the maximum
 8        result we've seen so far, since any number is present in the array.
 9
10        There are three cases:
11        1. A positive number is strictly beneficial.
12        2. A negative number could be beneficial or not.
13        3. A zero always resets your progress.
14
15        So, we can encode these three cases in keeping track of the min and
16        max so far. Either number has 3 parts:
17
18        1. We want to use curr, cause if the minimum and maximum are very small,
19        it's better to just restart.
20        2. Max * curr, because multiplying max by a large negative number or a large
21        positive number can create either a large positive or small negative number.
22        3. Min * curr, for the same reason.
23
24        At the end we return the max_so_far product we've seen.
25        """
26        if not nums:
27            return 0
28
29        result, max_so_far, min_so_far = nums[0], nums[0], nums[0]
30
31        for curr in nums[1:]:
32            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
33            min_so_far = min(curr, max_so_far * curr, min_so_far * curr)
34            max_so_far = temp_max
35
36            result = max(max_so_far, result)
37
38        return result

def maxProduct(self, nums: list[int]) -> int: View Source

 4    def maxProduct(self, nums: list[int]) -> int:
 5        """
 6        This problem asks us to return the maximum subarray product of an array.
 7        This requires us to keep track of the minimum result and the maximum
 8        result we've seen so far, since any number is present in the array.
 9
10        There are three cases:
11        1. A positive number is strictly beneficial.
12        2. A negative number could be beneficial or not.
13        3. A zero always resets your progress.
14
15        So, we can encode these three cases in keeping track of the min and
16        max so far. Either number has 3 parts:
17
18        1. We want to use curr, cause if the minimum and maximum are very small,
19        it's better to just restart.
20        2. Max * curr, because multiplying max by a large negative number or a large
21        positive number can create either a large positive or small negative number.
22        3. Min * curr, for the same reason.
23
24        At the end we return the max_so_far product we've seen.
25        """
26        if not nums:
27            return 0
28
29        result, max_so_far, min_so_far = nums[0], nums[0], nums[0]
30
31        for curr in nums[1:]:
32            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
33            min_so_far = min(curr, max_so_far * curr, min_so_far * curr)
34            max_so_far = temp_max
35
36            result = max(max_so_far, result)
37
38        return result

This problem asks us to return the maximum subarray product of an array. This requires us to keep track of the minimum result and the maximum result we've seen so far, since any number is present in the array.

There are three cases:

A positive number is strictly beneficial.
A negative number could be beneficial or not.
A zero always resets your progress.

So, we can encode these three cases in keeping track of the min and max so far. Either number has 3 parts:

We want to use curr, cause if the minimum and maximum are very small, it's better to just restart.
Max * curr, because multiplying max by a large negative number or a large positive number can create either a large positive or small negative number.
Min * curr, for the same reason.

At the end we return the max_so_far product we've seen.

def test(): View Source

44def test():
45    assert 2 + 2 == 4