Shiqi’s careless whisper

Finding the continuous sequence that has largest sum from a list of integers(or floats)

Long weekend could be boring, especially when you are just 3 weeks out of a major (relatively) surgery and can’t do serious outdoor activities. So I decided to dive into some of the basic algorithms and implement them in python. I used to just look at the pseudo code and thought “this is easy”. but for the past week I’ve been struggling to implement another problem (post in draft now) which really made me realize it could be much harder said than done. Admittedly some of those problems are really fundamental and most of the times people won’t bother to implement them because there are various libs to take advantage of (plus implementing your own version of same functionality from standard lib is really not a very good practice anyways). However, it is fun and really kills time. Besides, my biggest fear never is to be dumb but to be dumb without realizing it and the will the change it, struggling with those problems really help me to remind myself how bad of a coder I am and inspire me to improve it everyday.

So here is today’s problem:

Finding the continuous sequence that has largest sum from a list of integers(or floats)

The algorithm itself is pretty obvious: keep track of your sum, if it is below 0 then it won’t contribute to the max,

at that point keep what you have and then start a new iteration on the rest of the list.

My first implementation was to return the whole list, then I realized that the result will always be a subset of the original list

so just return the start and end index should be enough, it would save some space in this way.

Now it is arguable how to handle the situation when the max you can find is negative, which means you have nothing but negative numbers

in your list. I took a short cut here by returning an empty list in this case, my idea is that by returning an empty list I’m sending the message saying that you best choice in this situation is to not have anything from this list. An alternative could be scan the whole list once and initialize

the max_sum with the biggest element in the list. This won’t do harm to the O(n) time complexity.

Update: the wordpress coding syntax plugin reminds me that sum is a preserved keyword in python for sum function (shame on me that I even called that function in my code below for printing out without realizing it). Ahh, isn’t the highlighting nice? LOL

def largest_sum(self, list_of_int):
	max_sum = 0
	sum = 0
	i_max_start = 0
	i_max_end = -1
	current_start = 0		
	if list_of_int and type(list_of_int)==type([]):
		list_size = len(list_of_int)
		for index, item in enumerate(list_of_int):
			sum += item
			if sum > 0:
				if sum > max_sum:
					max_sum = sum
					i_max_end = index
					i_max_start = current_start				
			else:
				sum = 0
				if index < list_size-1:
					current_start = index +1
	return i_max_start, i_max_end				
 
def test_largest_sum(self):
	data = [[3,-7,5,-7,20,6,2,-6,4],
			[],
			[1,-2],
			[3,-7,1,-7,20,6,2,-1,4],
			[3,7,-1,-7,-20,6,2,-1,4],
			[3],
			[-7],
			[-5,10],
			[3,-2,4],
			'test',
			None]
	result = [(start, end) for (start, end) in map(self.largest_sum, data)]
	for index, d in enumerate(data):
		start, end = result[index]
		if end>=0:
			print sum(d[start:end+1]), d[start:end+1]
		else:
			print None, []

and here are the output:

28 [20, 6, 2]
None []
1 [1]
31 [20, 6, 2, -1, 4]
11 [6, 2, -1, 4]
3 [3]
None []
10 [10]
5 [3, -2, 4]
None []
None []

Something I thought about that could be interesting extension on this but yet have time to implement it or think it though:

Tags: algorithm, programming, python