Max-product scan with minimum tracking in Python

Single pass that keeps both the running maximum and running minimum product at each position.

File: kadane_max_product.py, 54 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

kadane_max_product.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kadane-max-product/. The authors are listed in prov/8EPB4B.jsonl.

from typing import Union

Number = Union[int, float]


def max_product(a: list[Number]) -> Number:
    """Return the largest product of a non-empty subarray of a.

    Precondition: a is not empty (raises ValueError otherwise).
    Cost: O(n) arithmetic operations, O(1) extra space. Python integers are exact,
    so with integer items the numbers can grow to about n times the item size.
    """
    if not a:
        raise ValueError("the array must not be empty")
    hi = lo = best = a[0]  # @line L1
    for j in range(1, len(a)):  # @line L2
        x = a[j]
        if x < 0:  # @line L3
            hi, lo = lo, hi
        hi = max(x, hi * x)  # @line L4
        lo = min(x, lo * x)  # @line L5
        best = max(best, hi)  # @line L6
    return best  # @line L7


def max_product_subarray(a: list[Number]) -> tuple[Number, int, int]:
    """Return (best, i, j), 0-based and inclusive, with the product of a[i:j + 1] equal to best.

    Same precondition and cost as max_product.
    """
    if not a:
        raise ValueError("the array must not be empty")
    hi = lo = best = a[0]
    hs = ls = 0
    bi = bj = 0
    for j in range(1, len(a)):
        x = a[j]
        if x < 0:
            hi, lo = lo, hi
            hs, ls = ls, hs
        if hi * x > x:
            hi = hi * x
        else:
            hi, hs = x, j
        if lo * x < x:
            lo = lo * x
        else:
            lo, ls = x, j
        if hi > best:
            best, bi, bj = hi, hs, j
    return best, bi, bj

test_kadane_max_product.py 46 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kadane-max-product/. The authors are listed in prov/8EPB4B.jsonl.

import math
import random

import pytest

from kadane_max_product import max_product, max_product_subarray


def brute(a: list[int]) -> int:
    return max(math.prod(a[i : j + 1]) for i in range(len(a)) for j in range(i, len(a)))


def test_example() -> None:
    assert max_product([2, 3, -2, 4, -1]) == 48
    assert max_product_subarray([2, 3, -2, 4, -1]) == (48, 0, 4)
    assert max_product([2, 3, -2, 4]) == 6
    assert max_product([-2, 3, -4]) == 24


def test_edges() -> None:
    assert max_product([-3]) == -3
    assert max_product([0]) == 0
    assert max_product([-2, 0, -1]) == 0
    assert max_product([0.5, 4, 0.5]) == 4
    assert max_product([-2, -3]) == 6
    assert max_product_subarray([-2, 0, -1]) == (0, 1, 1)
    with pytest.raises(ValueError):
        max_product([])
    with pytest.raises(ValueError):
        max_product_subarray([])


def test_against_brute_force() -> None:
    rng = random.Random(20261105)
    for _ in range(3000):
        n = rng.randrange(1, 14)
        a = [rng.randrange(-4, 5) for _ in range(n)]
        expected = brute(a)
        assert max_product(a) == expected
        best, i, j = max_product_subarray(a)
        assert best == expected
        assert 0 <= i <= j < n
        assert math.prod(a[i : j + 1]) == best

What the next level needs

the tests did not run in this build

Read the full page about Max-product scan with minimum tracking