Finds the maximum sum possible from picking a contiguous subsequence of an array in linear time

gistfile1.py

def highest_consecutive_sum(intarray):
	if not intarray:
		return None

	current_sum = intarray[0]
	current_start = 0
	current_end = 0
	highest_sum = current_sum
	highest_start = current_start
	highest_end = current_end

	for num in intarray[1:]:
		current_end += 1

		# Add the new element
		if current_sum <= 0:
			# The preceeding elements were useless to us
			current_start = current_end
			current_sum = num
		else:
			# Keep the preceeding elements
			current_sum += num

		# Compare to previous highest sums that we have ruined by trying to add
		# more elements
		if current_sum > highest_sum or \
				(
					# When there are multiple solutions, prefer the shortest ^_^
					current_sum == highest_sum
					and highest_end - highest_start > current_end - current_start
				):
			highest_sum = current_sum
			highest_start = current_start
			highest_end = current_end

	return highest_sum