# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

My experience with Kadane’s algorithm and it sharing similarities with this problem, I solved it quickly.

**What Went Wrong**

Debugging was slow, but overall I am pleased with the speed I solved this problem.

**What I Learned**

I learned how to alter Kadane’s algorithm to produce the maximum product as the output.

**Comments**

I was familiar with the approach to solving this problem, but sketching out potential solutions on paper allowed me to find the most efficient solution much faster.

# Algorithm Description

**Kadane’s Algorithm -** An iterative dynamic programming algorithm often used to find the maximum subarray. The algorithm tracks the local/current sum and the global sum. It iterates through the array and updates these values with the largest. Local/current sum either updates to the current array value or the current sum plus that value. Global sum either updates to the global sum or the current sum.

This iteration of the algorithm tracks the current minimum, current maximum, and global maximum, and instead of the largest sum, it returns the maximum product.

**Visual Examples**

Kadane’s Algorithm being performed on an array, click to view

# Solution Statistics

**Time Spent Coding**

7 minutes

**Time Complexity**

O(n) - Each element in the array is only visited once, resulting in the O(n) time complexity.

**Space Complexity**

O(1) - Only three new variables are created. The number of variables declared does not depend on the number of items in the list, resulting in the O(1) space complexity.

**Runtime Beats**

72.43% of other submissions

**Memory Beats**

98.57% of other sumbissions

# Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
def maxProduct(self, nums: List[int]) -> int:
# Negative numbers exist in this data set, so we can not use -infinity
# We must assign the first element to be the starting point for all variables
curMin = curMax = globalProd = nums[0]
for n in nums[1:]:
# To avoid accidentally multiplying by n twice, we must save the previous
# curMax in a variable
saveMax = curMax
curMax = max(curMax*n,curMin*n,n)
curMin = min(saveMax*n,curMin*n,n)
globalProd = max(curMax,curMin,globalProd)
return globalProd