Abstract / Summary

Given two integer lists find the maximum sum of products from picking any subsequences one from each list.

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 69% (200k+ 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 solves the “maximum dot product of two non-empty subsequences” problem using a top-down dynamic programming approach. A recursive helper deeper explores all alignment possibilities between the two input arrays while caching intermediate results to avoid redundant work. The algorithm returns the highest achievable dot product, and it contains a dedicated branch that correctly handles the situation where every feasible product is non-positive.

Core Recursive Exploration

@cache
def deeper(i, j):
    if i == len(nums1) or j == len(nums2):
        return 0

    one  = deeper(i + 1, j)
    two  = deeper(i, j + 1)
    both = max(0, nums1[i] * nums2[j]) + deeper(i + 1, j + 1)
    return max(one, two, both)

The function deeper receives two indices i and j, indicating the current positions in nums1 and nums2. The base case stops the recursion when either index reaches the end of its respective list, returning 0 because no further elements can contribute to the dot product.

Three alternatives are evaluated at each step:

• Skipping the element at i while keeping j unchanged (one).
• Skipping the element at j while keeping i unchanged (two).
• Pairing the two current elements (both). The product is taken only if it is non-negative; otherwise 0 is added, which effectively discards a detrimental pairing.

The maximum of these three choices is propagated upward, ensuring that the best partial result is retained.

Memoization for Reuse

The decorator @cache automatically stores the result of each (i, j) call. When the same state is encountered again, the cached value is returned instantly, eliminating exponential blow-up. This memoization transforms the naive exponential recursion into a polynomial-time solution, because each distinct pair of indices is processed at most once.

Handling of Non-Positive Scenarios

After the recursive phase finishes, the variable result holds the best dot product found under the rule that a paired product may be omitted if it is negative. The following block deals with the edge case where the recursion yields 0, which indicates that every possible pairing either produced a negative product or the algorithm chose to skip all pairings.

result = deeper(0, 0)
if result == 0:
    if max(nums1) <= 0:
        return max(nums1) * min(nums2)
    else:
        return min(nums1) * max(nums2)

Two distinct situations are covered:

• When all numbers in nums1 are non-positive, the largest (least negative) element of nums1 is multiplied by the smallest element of nums2. This yields the maximum possible product under the constraint that at least one pair must be selected.
• When nums1 contains at least one positive value but the recursion still returned 0, the smallest element of nums1 (which may be negative) is paired with the largest element of nums2. This again guarantees the highest attainable product when any positive pairing is impossible.

These branches guarantee that the function never returns 0 unless a zero product is truly optimal, thereby satisfying the problem’s requirement for a non-empty subsequence.

Performance Optimizations Observed

The primary optimization is the use of Python’s built-in functools.cache (or lru_cache) to memoize recursive calls. By caching results for each (i, j) pair, the algorithm avoids recomputation of overlapping subproblems, which is the hallmark of dynamic programming. The recursion depth is bounded by the sum of the lengths of the two input lists, and each recursive call performs only a constant amount of work beyond the cache lookup.

Another subtle optimization is the early elimination of negative products via max(0, nums1[i] * nums2[j]). By treating a negative product as zero, the algorithm prevents the propagation of detrimental values, reducing the number of states that need to be considered for optimality.

The special-case logic after the recursion also avoids unnecessary additional passes over the data. It directly computes the answer for the all-non-positive scenario using a single max and min operation on each list, which is O(n) in the size of the respective list but executed only once.

Edge Cases Explicitly Managed

The code correctly addresses the situation where the optimal dot product would be negative, which can happen when both arrays consist solely of non-positive numbers. In such cases, the recursion would otherwise return 0 because it prefers to drop negative pairings. The post-processing block forces a selection of a single pair, ensuring compliance with the requirement that the subsequences be non-empty.

It also handles the case where one array contains a mixture of positive and negative values, but any attempt to pair a positive element from nums1 with a suitable element from nums2 would still lead to a negative contribution. The fallback calculation selects the least harmful combination, guaranteeing the maximal possible product under those constraints.

Summary of Execution Flow

The algorithm begins by invoking deeper(0, 0). The recursive function explores all skip and pair decisions while caching results. Once the recursion completes, the main routine checks whether a positive dot product was found. If not, it computes the best possible product from a single pair based on the sign distribution of the input arrays. The final integer result is then returned.

Imagine two trains carrying boxes of toys labeled with different numbers. The goal is to pick some boxes from each train and multiply the numbers inside them to get the biggest score possible.

The code uses a little helper function that looks at the current boxes on both trains. For every set of boxes, it makes a choice. It can either skip the box on the first train, skip the box on the second train, or multiply the numbers in the current boxes together and add them to whatever big score comes from the boxes further down the line. Because we want the best result, the computer checks all these paths and keeps the largest number it finds.

The cache word is like a handy notebook. If the computer has already figured out the best score for a specific pair of boxes, it writes that answer down in the notebook so it can look it up later instead of doing the hard work all over again.

Sometimes, all the ways to multiply the numbers lead to a negative result. If the math ends up with zeroes but the boxes actually have numbers that could make a tiny bit of progress, the code checks the biggest and smallest numbers in both trains to make sure it picks the best pair even when everything is tricky.

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

Time: polynomial
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++		Java			Python		TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	Rust	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	suxrobGM				C#
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++

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