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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s