Max-contigious subarray

Max sum of a contigious subarray is the max sum of all the possible sub arrays.

This method however is very time consuming. Eg: It takes O(N^2) to just compute all the subarray and then takes another O(n) to compute sum of all. Overall time complexity is O(N^3) which is disastrous.

We can however improve it by divide and conquer.

The max sub contigous array sum is going to be max(left_half, max_subarray_sum_including_mid, right_half)

left_half is simply the answer of left half of the array. Same for right_half.

The max subarray which definitly included the arr[mid] is easy to calculate.

Now we know the answer to the left half, right half and the subarray which included the mid element. The overall result will be max of all three.

Here is the implementation:


def max_contiguous_array(arr, start_index, end_index):
	if start_index == end_index:
		return arr[start_index]
	elif start_index > end_index:
		return float('-inf')
	else:
		mid = (start_index + end_index) /2 

		left_subarray_max_sum = max_contiguous_array(arr, start_index, mid - 1)
		right_subarray_max_sum = max_contiguous_array(arr, mid + 1,end_index)

		current_sum = current_subarray_sum(arr, start_index, mid, end_index)

		return max(left_subarray_max_sum, right_subarray_max_sum, current_sum)


def current_subarray_sum(arr, left_index, mid, right_index):

	i = mid 
	j = mid + 1
	current_sum = 0
	left_max_sum = float('-inf')
	right_max_sum = float('-inf')
	while i >= left_index:
		current_sum += arr[i]

		left_max_sum = max(left_max_sum, current_sum)
		i -= 1
	current_sum = 0
	while j <= right_index:
		current_sum += arr[j]

		right_max_sum = max(right_max_sum, current_sum)
		j += 1

	return left_max_sum + right_max_sum 


arr = [-2,1,-3,4,-1,2,1,-5,4]

print max_contiguous_array(arr, 0, len(arr) -1)


Each function f(n) does O(n) work.
So, lets add all the complexity in all function calls:

O(n) + O(2 * n/2) + O(3 * n/3) ………..

= [O(n) + O(n) + O(n)……………..]

Total number of function calls are : Log(n).
So the total runtime complexity : n * log(n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s