The Maximum-Subarray Problem

# python
from collections import namedtuple
from datetime import datetime
from functools import partial
from math import inf as infinity
from math import log2
from typing import Sequence, Tuple

import random

# pypi
import altair
import pandas

# my stuff
from graeae import Timer
from graeae.visualization.altair_helpers import output_path, save_chart

TIMER = Timer()

SLUG = "the-maximum-subarray-problem"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)

MAXIMUM_SUBARRAY = Tuple[int, int, float, int]
Case = namedtuple("Case", ["inputs", "left", "right", "max"])

Plot = namedtuple("Plot", ["height", "width"], defaults=[700, 1000])
PLOT = Plot()

Output = namedtuple("Output", ["start", "end", "gain", "runtime"])

CASE_ONE = Case([100, 113, 110, 85, 105, 102, 86, 63, 81,
                 101, 94, 106, 101, 79, 94, 90, 97],
                left=7,
                right=11,
                max=43)

x = CASE_ONE.inputs
changes = [0] + [x[index + 1] - x[index] for index in range(len(x) - 1)]

frame = pandas.DataFrame({"Numbers": x,
                          "Change": changes})

melted = frame.reset_index()
melted = melted.melt(id_vars=["index"], value_vars=["Numbers", "Change"] , var_name="Data Source", value_name="Data")
chart = altair.Chart(melted).mark_line().encode(
    x=altair.X("index", type="quantitative"),
    y=altair.Y("Data", type="quantitative"),
    color="Data Source").properties(
        title="Sample Input One", width=PLOT.width, height=525)

save_it(chart, "sample-input-one")

def brute_force_maximum_subarray(source: Sequence) -> Output:
    """Finds the subarray with maximum gain

    Args:
     source: sequence with sub-array to maximize

    Returns:
     (left-max-index, right-max-index, gain, count)
    """
    best_left = best_right = None
    best_gain = -infinity
    count = 0
    for left in range(len(source) - 1):
        for right in range(left + 1, len(source)):
            count += 1
            gain = source[right] - source[left]
            if gain > best_gain:
                best_left, best_right, best_gain = left, right, gain
    return Output(best_left, best_right, best_gain, count)

n = len(CASE_ONE.inputs)
print(f"n = {n}")
output = brute_force_maximum_subarray(CASE_ONE.inputs)
assert output.start == CASE_ONE.left
assert output.end == CASE_ONE.right
assert output.gain == CASE_ONE.max
print(f"count = {output.runtime}")
print(f"n(n-1)/2 = {int((n * (n - 1))/2)}")
print(f"n^2 = {n**2}")

def max_subarray_2(source: Sequence) -> Output:
    """Gets the maximal subarray

    This is an alternate version that doesn't use recursion or brute-force

    Args:
     source: sequence to maximize

    Returns:
     left-index, right-index, gain, count
    """
    count = 1
    best_total = -infinity
    best_start = best_end = 0
    current_total = 0

    changes = [source[index + 1] - source[index] for index in range(len(source) - 1)]
    for here, value_here in enumerate(changes):
        count += 1
        if current_total <= 0:
            current_start = here
            current_total = value_here
        else:
            current_total += value_here

        if current_total > best_total:
            best_total = current_total
            best_start = current_start
            best_end = here + 1
    return Output(best_start, best_end, best_total, count)

n = len(CASE_ONE.inputs)
print(f"n = {n}")
left, right, gain, count = max_subarray_2(CASE_ONE.inputs)
assert left == CASE_ONE.left, f"Expected: {CASE_ONE.left}, Actual: {left}"
assert right == CASE_ONE.right, f"Expected: {CASE_ONE.right}, Actual: {right}"
assert gain == CASE_ONE.max, f"Expected: {CASE_ONE.max}, Actual: {gain}"
print(f"left: {left}, right: {right}, gain: {gain}")

print(f"Count: {count}")

runtimes = pandas.DataFrame({"Brute Force": brutes,
                             "Divide and Conquer": divided,
                             "Linear": linear,
                             "Input Size": counts})

melted = runtimes.melt(id_vars=["Input Size"],
                       value_vars=["Brute Force", "Divide and Conquer", "Linear"],
                       var_name="Algorithm", value_name="Comparisons")

chart = altair.Chart(melted).mark_line(point=altair.OverlayMarkDef()).encode(
    x=altair.X("Input Size", type="quantitative"),
    y=altair.Y("Comparisons", type="quantitative"),
    color="Algorithm"
).properties(
    title="Comparison Counts", width=PLOT.width, height=525)

save_it(chart, "algorithm_comparisons")

linear_more = linear[:]
divided_more = divided[:]
counts_more = counts[:]

for exponent in range(6, 10):
    count = 10**exponent
    title = f"n = {count:,}"
    underline = "=" * len(title)
    print(f"\n{title}")
    print(underline)

    inputs = list(range(count))
    inputs = random.choices(inputs, k=count)

    linear_more.append(run_thing(max_subarray_2, inputs, "Linear"))
    divided_more.append(run_thing(maximum_subarray, inputs, "Divide and Conquer"))
    counts_more.append(count)

longtimes = pandas.DataFrame({"Linear": linear_more,
                              "Divide & Conquer": divided_more,
                              "Input Size": counts_more})

melted = longtimes.melt(id_vars=["Input Size"],
                       value_vars=["Divide & Conquer", "Linear"],
                       var_name="Algorithm", value_name="Comparisons")
chart = altair.Chart(melted).mark_line(point=altair.OverlayMarkDef()).encode(
    x=altair.X("Input Size", type="quantitative"),
    y=altair.Y("Comparisons", type="quantitative"),
    color="Algorithm").properties(
        title="Comparison Counts", width=PLOT.width, height=525)

save_it(chart, "longer_algorithm_comparisons")