Largest Sum Contiguous Subarray

Kadane’s Algorithm:

By using this algorithm, we can determine the solution in the most optimal way.

Approach:

• We take an array and assign max_sum = 0 and max_val = first element of our list

Eg: a=[-13, -3, 4, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]
max_sum = 0
max_yet = a[0]

• Now we start a loop and iterate through each element and calculate which is the maximum value, either the max_sum value + element value or the element value alone and store it in a temp variable. then we will assign this temp value as our new max_sum and if temp is greater than max_yet, we will change the max_yet to temp.

Eg: when i = 0, we are at a[0] i.e., -13
temp = maximum of 0+(-13) and -13.
Now our max_sum becomes -13 and max_yet is already -13

In second iteration,
when i = 1, a[0] = -3
temp = Maximum of -13+(-3) and -3
now our max_sum becomes -3 and max_yet will be updated to -3

and so on

• After the loop gets finished, we are left with the maximum of subarray value stored in the max_yet variable. so we return it.

a=[-13, -3, 4, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]
max_sum = 0
max_yet = a[0]
for i in range(len(a)):
    max_sum = max(max_sum+a[i],a[i])
    if max_sum > max_yet:
        max_yet = max_sum
print(max_yet)

Output:

4