kadane.py

# Kadane's algorithm
def largest(a):
	max_current = -100
	maxvalue = -100

	for i in range(len(a)):
		if (max_current < 0):
			max_current = a[i]
			currenti = i
			currentj = i
		else:
			max_current += a[i]
			currentj = i

		if max_current > maxvalue:
			maxvalue = max_current
			besti = currenti
			bestj = currentj

	return maxvalue, besti, bestj


print largest([-1, -2, 3, 4, -5, 6])
print largest([-7, 4, -2, 5, 3, -6, 8, -9])