Sunday, September 20, 2015

Python Code for Maximum Sum Subarray Problem

"In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6." --Wikipedia

A linear time solution was proposed by Jay Kadane and was hence forth named as Kadane's Algorithm. The algorithm paradigm followed is Dynamic Programming. Here I have given you the python code for this problem.



0 comments :

Post a Comment

Follow Me!

Followers

Visitor Map