|
| 1 | +#Kadane's Algorithm |
| 2 | + |
| 3 | +Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this) Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far |
| 4 | +##Install |
| 5 | + |
| 6 | +``` |
| 7 | +pip install allalgorithms |
| 8 | +``` |
| 9 | + |
| 10 | +##Usage |
| 11 | + |
| 12 | +```py |
| 13 | +from allalgorithms.subarrayimport kadane |
| 14 | + |
| 15 | +arr= [-2,1,2,7,10,77] |
| 16 | + |
| 17 | +print(kadane.maxsum_subarray(arr)) |
| 18 | +# -> 97 |
| 19 | + |
| 20 | +print(kadane.returnArray(arr)) |
| 21 | +# -> [97, [1, 2, 7, 10, 77]] |
| 22 | +``` |
| 23 | + |
| 24 | +##API |
| 25 | + |
| 26 | +###maxsum_subarray(array) |
| 27 | + |
| 28 | +>Return sum of maximum contigious subarray |
| 29 | +
|
| 30 | +###returnArray(array) |
| 31 | + |
| 32 | +>Return sum along with the respective subarray |
| 33 | +
|
| 34 | +#####Params: |
| 35 | + |
| 36 | +-`array`: Array (may contain negative elements) |