"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