# max profit #max sub-array sum is similar

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[0], arr[1] .. 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[3] is negative i.e. all 4 sub-array sums ending in arr[3] are all negative, then B[4] 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[3], 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