FilesExpand file tree

master

/

maxproductsubarray.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (22 loc) · 653 Bytes

master

/

maxproductsubarray.py

Copy path

Top

File metadata and controls

• Code
• Blame

24 lines (22 loc) · 653 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# http://www.geeksforgeeks.org/maximum-product-subarray/

def max_product(input):

max_ending = 1

min_ending = 1

max_so_far = 1

for i in input:

if i > 0:

max_ending = max_ending * i

min_ending = min(min_ending*i, 1)

elif i == 0:

max_ending = 1

min_ending = 1

else:

t = max_ending

max_ending = max(min_ending*i, 1)

min_ending = t * i

if max_so_far < max_ending:

max_so_far = max_ending

return max_so_far

if __name__ == '__main__':

input = [-6,-3,8,-9,-1,-1,3,6,9,0,3,-1]

print(max_product(input))