# 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`