contiguous.py

import random
# Given a (possible) large list of random numbers (positive and
# negative) find the largest sum of a contiguous sub-sequence.
#
# From chapter 8 of programming pearls. My attempt before reading past
# the first page.

def largestsub(lst):
    prev = 0
    largest = float("-inf")
    for v in lst:
        prev = max(prev+v, v)
        largest = max(prev, largest)
    return largest

def naive(lst):
    return max(sum(lst[x:y+1]) for x in range(len(lst)) for y in range(x,len(lst)))

sample1 = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
sample2 = (random.randint(-128, 127) for x in xrange(1000000))
    
print naive(sample1)
# print naive(sample2) # Would take quite a lot of time to run

print largestsub(sample1)
print largestsub(sample2)