FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/Python/maximum-product-subarray.py at master · pythonpeixun/LeetCode-Solutions · GitHub

27 lines (24 loc) · 908 Bytes

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

# Time: O(n)

# Space: O(1)

class Solution(object):

# @param A, a list of integers

# @return an integer

def maxProduct(self, A):

global_max, local_max, local_min = float("-inf"), 1, 1

for x in A:

local_max, local_min = max(x, local_max * x, local_min * x), min(x, local_max * x, local_min * x)

global_max = max(global_max, local_max)

return global_max

class Solution2(object):

# @param A, a list of integers

# @return an integer

def maxProduct(self, A):

global_max, local_max, local_min = float("-inf"), 1, 1

for x in A:

local_max = max(1, local_max)

if x > 0:

local_max, local_min = local_max * x, local_min * x

else:

local_max, local_min = local_min * x, local_max * x

global_max = max(global_max, local_max)

return global_max

Back | FazBrowse Home | New Git URL