max_sum_path.py: Script that calculates the maximum sum path between two lists of integers.

max_sum_path.py

from typing import (
    Callable,
    Iterator,
    Generator,
    Protocol,
    Tuple,
    TypeVar,
)


Number = TypeVar('Number', int, float)


class Vector(Protocol[Number]):
    # Any object that implements these three methods with a compatible signature
    # is considered to be compatible with "Vector".

    def __iter__(self) -> Iterator[Number]:
        ...

    def __getitem__(self, idx: int) -> Number:
        ...

    def __setitem__(self, idx: int, val: Number) -> None:
        ...

    def __len__(self) -> int:
        ...

    def append(self, new_item: Number) -> None:
        ...


def _cummulative_sum(vector: Vector[Number]) -> Generator[Number, None, None]:
    """Helper function that yields the cummulative sum of a Vector[Number] variable."""
    acc: Number = 0

    for value in vector:
        acc += value
        yield acc


def _print_path_section(vector: Vector[Number], start: Number, end: Number) -> str:
    """Helper function that builds the string for a section of the maximum sum path."""
    path_section: str = ''

    for i in range(int(start), int(end + 1)):
        path_section += f'({i},{vector[i]}) -> '

    return path_section


def _get_intersection_indexes(
    iter_1: Vector[Number],
    iter_2: Vector[Number]
) -> Tuple[Vector[int], Vector[int]]:
    """Helper function that finds the intersection points in O(m+n)."""
    print('Making intersection...')

    i: int = 0
    j: int = 0
    indexes_1: Vector[int] = []
    indexes_2: Vector[int] = []

    while i < len(iter_1) and j < len(iter_2):

        if iter_1[i] == iter_2[j]:  # If there's a intersection between, store index of both arrays
            indexes_1.append(i)
            indexes_2.append(j)
            i += 1
            j += 1
        elif iter_1[i] > iter_2[j]:  # else increase the index of array containing small number
            j += 1
        elif iter_1[i] < iter_2[j]:
            i += 1

    return indexes_1, indexes_2


def build_max_sum_path(iter_1: Vector[Number], iter_2: Vector[Number]) -> Tuple[Number, str]:
    """Implements the maximum sum path problem between two lists of sizes n and m, respectively, in O(m+n).
    1. Evaluates a cumulative sum array for both arrays.
    2. Then finds the intersection point in O(m+n).
    3. Checks which array has maximum sum between two intersection point.
    """
    cond_iterable: Callable = lambda _iterable: isinstance(_iterable, (list, tuple)) and len(_iterable) > 0

    if not (cond_iterable(iter_1) and cond_iterable(iter_2)):
        return 0, ''

    n: int = len(iter_1)
    m: int = len(iter_2)
    sum_1: Vector[Number] = list(_cummulative_sum(iter_1))
    sum_2: Vector[Number] = list(_cummulative_sum(iter_2))

    indexes_1, indexes_2 = _get_intersection_indexes(iter_1, iter_2)

    print('Evaluating max sum path...')

    path: str = ''
    max_sum: Number = 0
    index_1: int = 0
    index_2: int = 0

    i: int = 0

    while i < len(indexes_1):

        index_1 = indexes_1[i]
        index_2 = indexes_2[i]

        if i == 0:
            if sum_1[index_1] > sum_2[index_2]:  # Check which array has greter sum at first intersection
                max_sum += sum_1[index_1]
                path += _print_path_section(iter_1, 0, index_1)
            else:
                max_sum += sum_2[index_2]
                path += _print_path_section(iter_2, 0, index_2)

            i += 1
        else:
            # Checks which array has greater sum betweem intersection
            if sum_1[index_1] - sum_2[indexes_1[i - 1]] > sum_2[index_2] - sum_2[indexes_2[i - 1]]:
                max_sum += sum_1[index_1] - sum_1[indexes_1[i - 1]]
                path += _print_path_section(iter_1, indexes_1[i - 1] + 1, index_1)
            else:
                max_sum += sum_2[index_2] - sum_2[indexes_2[i - 1]]
                path += _print_path_section(iter_2, indexes_2[i - 1] + 1, index_2)

            i += 1

    # Checks which array has greater sum at last intersection
    if sum_1[n - 1] - sum_2[index_1] > sum_2[m - 1] - sum_2[index_2]:
        max_sum += sum_1[n - 1] - sum_1[index_1]
        path += _print_path_section(iter_1, index_1 + 1, n - 1)
    else:
        max_sum += sum_2[m - 1] - sum_2[index_2]
        path += _print_path_section(iter_2, index_2 + 1, m - 1)

    return max_sum, path[:-4]


if __name__ == '__main__':
    x = [2, 3, 7, 10, 12]
    y = [1, 5, 7, 8]

    sum_value, max_sum_path = build_max_sum_path(x, y)

    print(f'Maximum sum is {sum_value}')
    print(f'Maximum sum path is {max_sum_path}')