NeoAlgo/Python/other/Maximum_Product_Subarray.py at master · leoshrey/NeoAlgo · GitHub

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
'''
Given an array Arr that contains N integers (may be positive, negative or zero).
Find the product of the maximum product subarray.

Example 1:

Input:{6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is  6, -3, -10 which gives product as 180.
Example 2:

Input:{2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is 2, 3, 4, 5 which gives product as 120.

'''
def maximum_product_subarray(arr):
    arr2 = arr[::-1]
    for i in range(1, len(arr)):
        arr[i] *= arr[i - 1] or 1
        arr2[i] *= arr2[i - 1] or 1
    return max(arr + arr2)

if __name__ == "__main__":
    arr = list(map(int,input("Enter the number: ").split()))
    print("Maximum Subarray product is ",maximum_product_subarray(arr))

'''
Time complexcity  = O(n)
space complexcity = O(1)

INPUT
Enter the Number: 6 -3 -10 0 2

OUTPUT
Maximum Subarray product is 180
'''