FilesExpand file tree

 master

/

max_product_subarray.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (53 loc) · 1.77 KB

 master

/

max_product_subarray.py

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (53 loc) · 1.77 KB

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

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

"""

Find the contiguous subarray within an array

(containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],

the contiguous subarray [2,3] has the largest product = 6.

"""

def max_product(nums):

"""

:type nums: List[int]

:rtype: int

"""

lmin = lmax = gmax = nums[0]

for i in range(len(nums)):

t1 = nums[i] * lmax

t2 = nums[i] * lmin

lmax = max(max(t1, t2), nums[i])

lmin = min(min(t1, t2), nums[i])

gmax = max(gmax, lmax)

'''

Another approach that would print max product and the subarray

Examples:

subarray_with_max_product([2,3,6,-1,-1,9,5])

#=> max_product_so_far: 45, [-1, -1, 9, 5]

subarray_with_max_product([-2,-3,6,0,-7,-5])

#=> max_product_so_far: 36, [-2, -3, 6]

subarray_with_max_product([-4,-3,-2,-1])

#=> max_product_so_far: 24, [-4, -3, -2, -1]

subarray_with_max_product([-3,0,1])

#=> max_product_so_far: 1, [1]

'''

def subarray_with_max_product(arr):

''' arr is list of positive/negative numbers '''

l = len(arr)

product_so_far = max_product_end = 1

max_start_i = 0

so_far_start_i = so_far_end_i = 0

all_negative_flag = True

for i in range(l):

max_product_end *= arr[i]

if arr[i] > 0: all_negative_flag = False

if max_product_end <= 0:

max_product_end = arr[i]

max_start_i = i

if product_so_far <= max_product_end:

product_so_far = max_product_end

so_far_end_i = i

so_far_start_i = max_start_i

if all_negative_flag:

print "max_product_so_far: %s, %s" % \

(reduce(lambda x, y: x * y, arr), arr)

else:

print "max_product_so_far: %s, %s" % (product_so_far,\

arr[so_far_start_i:so_far_end_i + 1])