maximum subarray


See On Github

Data

Tags

Source Code

from random import shuffle

'''
The maximum subarray problem is the task of finding the contiguous subarray within a
1D array of numbers (containing at least one positive number) which has the largest sum.

following implementation is the Dynamic Programming Approach
Time Complexity is O(n)
'''

def kadane(arr):
	size = len(arr)
	curr_max = arr[0]
	max_so_far = arr[0]
	for i in range(1, size):
	    curr_max = max(curr_max+arr[i],arr[i])
	    max_so_far = max(curr_max,max_so_far)
	return max_so_far

if __name__ == '__main__':
	array = list(range(10, -10, -1))
	shuffle(array)
	print "List: " + str(array)
	print "Maximum Sum of SubArrays: "
	response = kadane(array)
	print response
import unittest
from kadane import kadane

class TestKadanesAlgorithm(unittest.TestCase):
    def setUp(self):
        self.arrays = [
            [-2, 1, -3, 4, -1, 2, 1, -5, 4],
            [2, 3, 7, -5, -1, 4, -10]
        ]
        self.expected_results = [6, 12]

    def test_kadanes_algorithm(self):
        for i, arr in enumerate(self.arrays):
            self.assertEqual(kadane(arr), self.expected_results[i])


if __name__ == '__main__':
    unittest.main()