about summary refs log tree commit diff
path: root/scratch/facebook/largest-contiguous-sum.py
blob: 7761bf1c61df92dd690bab640bdf39d0ff90a458 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_sum(xs):
    result = float('-inf')
    streak = 0
    for x in xs:
        result = max(result, streak, x)
        if streak + x <= 0:
            streak = x
        else:
            streak += x
    return result


x = [2,-8,3,-2,4,-10]
assert find_sum(x) == 5
print("Success!")