LeetCode #152 - Max Product Subarray

1
Example input: [2, 3, -2, 4]
2
Subarrays:
3
[2] → 2
4
[2, 3] → 6
5
[2, 3, -2] → -12
6
[3, -2] → -6
7
[-2, 4] → -8
8
Max = 6
9
Optimized Approach
10

11
Explanation:
12
Based on the number of negative elements:
13

14
If all positives → result is the product of the entire array.
15

16
If even number of negatives → product of entire array is positive.
17

18
If odd number of negatives → remove one negative (either from start or end) to make the product positive.
19

20
Handle 0s by splitting the array into subarrays and applying the above logic on each.
21

22
Algorithm:
23
prefix_product = 1
24
suffix_product = 1
25
max_product = nums[0]
26

27
for i in range(len(nums)):
28
    prefix_product *= nums[i]
29
    suffix_product *= nums[-1-i]
30
    max_product = max(max_product, prefix_product, suffix_product)
31
    if nums[i] == 0:
32
        prefix_product = 1
33
    if nums[-1-i] == 0:
34
        suffix_product = 1
35
Time Complexity: O(N) – Single pass
36

37
Space Complexity: O(1) – Only scalar variables used
38

39
Example/Dry Run:
40
Input: [-2, 3, 4, -1, 0, -2, 3, 1, 4, 0, 4, 6, -1, 4]
41
Break on zeros → [[-2,3,4,-1], [-2,3,1,4], [4,6,-1,4]]
42
Answer = max of all segment max products
43

44
Best / Final Optimized Approach (Kadane-style)
45

46
Explanation:
47
Track the maximum and minimum product ending at the current index. Negative numbers can flip max to min and vice versa. This ensures handling of alternating signs.
48

49
Algorithm:
50
prod1 = prod2 = result = nums[0]
51

52
for i in range(1, len(nums)):
53
    current = nums[i]
54
    temp = max(current, current * prod1, current * prod2)
55
    prod2 = min(current, current * prod1, current * prod2)
56
    prod1 = temp
57
    result = max(result, prod1)
58
Time Complexity: O(N) – Single loop
59

60
Space Complexity: O(1) – Constant number of variables
61

62
Example/Dry Run:
63
Input: [1, 2, -3, 0, -4, -5]
64

65
Step 1: prod1 = prod2 = result = 1
66
i = 1: nums[i] = 2 → temp = max(2, 2*1, 2*1) = 2
67
        prod1 = 2, prod2 = 2, result = 2
68
i = 2: nums[i] = -3 → temp = max(-3, -6, -6) = -3
69
        prod1 = -3, prod2 = -6, result = 2
70
i = 3: nums[i] = 0 → temp = 0 → reset
71
i = 4: nums[i] = -4 → ...
72
Final result: 20
73

74
---
75

76
## 📊 Complexity Analysis
77

78
| Approach      | Time Complexity | Space Complexity |
79
| ------------- | --------------- | ---------------- |
80
| Brute Force   | O(N²)           | O(1)             |
81
| Optimized     | O(N)            | O(1)             |
82
| Best Approach | O(N)            | O(1)             |
83

84
---
85

86
## 📉 Optimization Ideas
87

88
- Use rolling variables instead of arrays to track max/min products.
89
- Restart subarray product after encountering 0 to ensure correct segmentation.
90
- Can further optimize by using prefix/suffix scans with early exits.
91

92
---
93

94
## 📌 Example Walkthroughs & Dry Runs
95

96
plaintext
97
Example:
98
Input: [2, 3, -2, 4]
99
Process:
100
→ 2 → max = 2
101
→ 2×3 = 6 → max = 6
102
→ 6×(-2) = -12 → becomes min
103
→ restart with 4 → max = 6
104
Output: 6
105

106
Another:
107
Input: [1, 2, -3, 0, -4, -5]
108
→ Subarray after 0 = [-4, -5] → product = 20
109
Output: 20
110

111
---
112

113
## 🔗 Additional Resources
114

115
- [Kadane’s Algorithm for Maximum Sum](https://en.wikipedia.org/wiki/Maximum_subarray_problem)
116

117
---
118

119
Author: Abdul Wahab
120
Date: 19/07/2025