https://github.com/tiger40490/repo1/tree/py1/py/array has a more correct solution.
https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ has a simpler solution, to be understood.
- special case: If all numbers are negative, then final answer is the “smallest” negative number as a tiny array.
- special case: If all numbers are positive, then final answer is the entire original array
- so the tricky case must have positive negative and positive numbers.
Input array has arr, arr .. arr[n]. Here’s my explanation of Kadene’s algo
- let’s denote maxSubsumEndingAt(i) as B[i]
- B[i+1] == max(B[i] + arr[i+1] –vs– arr[i+1] )
- if B is negative i.e. all 4 sub-array sums ending in arr are all negative, then B should not include any of them. We can discard them for good and “start afresh“(while keeping the global maxSumSeen)
- else, there exists a “positive” sub-array ending at arr, so we keep growing it until it becomes negative.
- (See github code) I can imagine a left-marker, the start of the current max subarray. We will move the right marker to grow the sub-array if the current sub-array is useful i.e. positive. Otherwise, we start afresh and the left marker is set to right-marker