1. Kadane’s Algorithm #

Created Monday 27 April 2020

• Largest Sum Subarray - return the maximum sum.

Algorithm #

1. Traverse, but ignore. non-positive values at the start of the array.
2. Select the first +ve chunk of positive values at the start. Store the sum in a global_sum, which stores maximum sum.
3. If you encouter a negative value, you have two choices:
   1. Include it - but only if the new sum(sum_till_now + value) is positive.
   2. Exclude it - If a. is not possible. Subarray temp_sum becomes zero, and a new subarray is started, from the nearest incoming positive number.
4. Continue traversal and step 3.
5. The value global_sum after traversing the array is the maxium sum.

Note: Step 1 is unecessary, as it is already covered in the remaining steps.

Motivation #

• Take a general example of an array with a lot of elements(more than 2).
• Clear your mind by removing the non positive values at start.