Abstract / Summary

Find the largest product that can be made by multiplying a group of consecutive numbers in a list of integers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 37% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method maxProduct that computes the maximum product of any contiguous sub-array within the input list nums. The algorithm proceeds in a single forward traversal, maintaining a running product of the current segment and a secondary product that captures the effect of the most recent negative number. By updating a global best value at each step, the method ultimately returns the largest product encountered.

Core Logic

The method begins by initializing three variables: best holds the best product seen so far and is seeded with the first element of the input; product accumulates the product of the current non-zero segment; negative stores the product of the segment up to the first negative number when such a number exists.

best = nums[0]
product  = 1
negative = 0

The main loop iterates over each integer n in nums. For every element, the running product product is multiplied by n. Simultaneously, negative is multiplied by n only when it has already been activated (i.e., when it is non-zero).

for n in nums:
    product  *= n
    negative *= n

After updating the products, the algorithm compares the current product with best and records the larger value.

best = max(best, product)

When a zero is encountered, the current segment ends because any product that includes zero collapses to zero. The code resets product to the neutral multiplicative identity 1 and clears negative to 0, then proceeds to the next element. This reset ensures that subsequent elements start a fresh segment without being tainted by the zero.

if product == 0:
    product  = 1
    negative = 0
    continue

If negative is active (non-zero), the algorithm also evaluates it against best. This step captures the scenario where discarding the prefix up to the first negative number yields a larger product, which is a common pattern when the segment contains an even number of negatives.

if negative != 0:
    best = max(best, negative)

The activation of negative occurs when the current element n is negative and negative has not yet been set. In that case, negative is initialized to 1 so that subsequent multiplications will correctly represent the product from the first negative onward.

if n < 0 and negative == 0:
    negative = 1

Finally, after processing all elements, the method returns the recorded maximum product.

return best

Edge Cases Handled

The code explicitly addresses the presence of zeros by resetting the running products, thereby preventing a zero from contaminating later calculations. This handling also covers the situation where the input consists solely of zeros; the initial best value (the first zero) will be returned.

When the array contains a single element, the initialization of best with nums[0] ensures that the method returns that element, regardless of its sign.

For arrays that contain only negative numbers, the logic that tracks negative enables the algorithm to consider the product of the sub-array that excludes the leading negative element, which can be larger when the count of negatives is odd.

If the input includes a mixture of positive, negative, and zero values, the combination of resetting on zero and evaluating both product and negative at each step guarantees that the maximum product of any contiguous segment is captured.

Performance Optimizations

The implementation achieves its goal with a single pass over the input list, avoiding any nested loops or repeated scans. By maintaining only three scalar variables, it operates with constant auxiliary storage, regardless of the size of nums.

The early exit on zero (continue) prevents unnecessary checks for negative in the same iteration, reducing the amount of work performed after a segment terminates.

The conditional activation of negative (only when a negative number is first seen) avoids needless multiplications when the segment contains no negatives, thereby saving arithmetic operations.

Overall, the design balances simplicity with efficiency, delivering the required result while minimizing both time spent in the loop and memory overhead.

Imagine a box of number blocks that you can multiply together to build a tower. Each block has a number written on it, and the goal is to make the biggest number possible by picking a group of blocks that sit right next to each other in a line.

First, the code picks the very first block and calls that the best one found so far. Then, it starts walking down the line of blocks one by one. It keeps a running total by multiplying the blocks together as it goes. If it hits a block with the number zero, it hits a reset button because multiplying by zero would turn everything into a tiny zero.

There is a special trick for the blocks with minus signs. When moving across negative numbers, the code keeps track of a second group to see if flipping a negative sign might help squeeze out a larger number later on. At every single step, it compares the new total to the best one found before. If the new one is bigger, it keeps that one instead. It keeps doing this until it reaches the very last block in the line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#		Rust	JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis							JS
	FelixFan1122				C#
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02					C
	vthwang			Java
	wisdompeak	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality