First week having algorithms and data structures – our assignment is regarding the infamous Maximum subarray problem. In all simplicity the assignment is as follows:

The input is a vector x of n floating-point numbers; the output is the maximum sum found in any contiguous subvector of the input. For instance if the input vector contains these ten elements

then the algorithm returns the sum of x[2..6], or 187.

This problem can be solved in many different ways – worst cases we’ve been given compute this in as bad as O(n^3) – best case is a linear algorithm doing this in O(n). The linear algorithm is as follows (Python code):

def partialMaxSum(set):
	maxsofar = 0
	maxendinghere = 0
	for i in range(len(set)):
		maxendinghere = max(maxendinghere + set[i], 0)
		if maxendinghere > maxsofar:
			maxsofar = maxendinghere

	return maxsofar

The problem

The problem then comes when trying to find the solution to a similiar problem – extend the above to 2 dimensions. The best solution found to this problem so far manages to do this in O(n^3) – My first draft did this in O(n^4) – so there’s a vast improvement to get. I managed to get the O(n^3) solution working in Python as well (if one wishes to count additions this is (n^3+n^2)/2 to be scaringly exact), with much much more meaningful variables than the original C code I ported it from

def partialMaxSumOverMatrix(matrix):
	maxsofar = 0
	n = len(matrix)
	set = range(n)
	for rowStart in set:
		columnSums = []
		for rowEnd in range(rowStart, n):
			maxEndingAtRowEnd = 0
			maxStartingAtRowStart = 0
			for column in set:
				if column >= len(columnSums):
					columnSums.append(0)
					
				columnSums[column] += matrix[rowEnd][column]
				maxEndingAtRowEnd = maxEndingAtRowEnd + columnSums[column]
				
				if maxEndingAtRowEnd > maxStartingAtRowStart:
					maxStartingAtRowStart = maxEndingAtRowEnd

				maxEndingAtRowEnd = max(maxEndingAtRowEnd, 0)

			maxsofar = max(maxsofar, maxStartingAtRowStart)
			
	return maxsofar

This solution is quite brilliant. It works as follows:

For each row, rowStart, it builds up a new cummulative array, columnSums, now iterating from rowStart to n (number of rows and columns) into rowEnd – for every column at the rowEnd’th row it sums the value at (rowEnd,column) with columnSums[column]. Now spanning the test strip further over these columns (and rowStart – rowEnd rows) if the value of this exceeds the current maximum found, maxsofar, this value is stored. If the current working value is negative it is reset to 0. At the end of this all possible options have been tried and the maximum has been found.

Please note, my python skills are very bad – and I usually code C#, Java, PHP or anything else that hides the algorithm more than Python, so this was a first go at this language for me.

For those interested, and speak Danish, the final assignment is available for download.