python version of max subarray solution

max_subarray.py

#! /usr/bin/python3

import random

# A quick test of a linear max subarray algorithm

class Partial:
  """Named collection corresponding to a partial sum of a sequence of deltas"""
  def __init__(self, value, index):
    self.value = value
    self.index = index


class Subarray:
  """Named collection corresponding to a subarray and its sum.

  Convenience to keep all the values straight."""

  def __init__(self, diff, start, end):
    """Usual python index semantics: start is inclusive, end exclusive."""
    self.diff = diff
    self.start = start
    self.end = end

  def copy(self):
    """Avoid aliasing issues."""
    return Subarray(self.diff, self.start, self.end)
  
  def __str__(self):
    return "Difference of "+str(self.diff)+" from ["+str(self.start)+", "+str(self.end)+")"


def partials(deltas):
  """Return the running partial sums from a sequence of deltas.

  Linear with respect to deltas."""

  running = 0
  index = 0

  for d in deltas:
    running += d
    yield Partial(running, index)
    index += 1


def max_subarray(deltas):
  """a linear maximal subarray algorithm for a finite sequence of deltas."""

  max = Subarray(0, 0, 0)
  current = Subarray(0, 0, 0)
  prev = None

  for p in partials(deltas):
    # inital element
    if prev == None:
      prev = p
      continue # need to init prev

    # Update eager current
    current.diff += (p.value - prev.value)
    current.end = p.index
    prev = p

    # Update lazy max if current has exceeded it
    if current.diff > max.diff:
      max = current.copy()

    # Move eager current forward if it becomes negative or 0
    if current.diff <= 0:
      current = Subarray(0, p.index, p.index)

  return max

def n_rands(n, size):
    for i in range(n):
        yield random.randrange(-size, size)

if __name__ == "__main__":
  data = list(n_rands(500, 100))
  print("Data: "+str(data))
  print("Max: "+str(max_subarray(data)))