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

--

--

--

Looking for my next opportunity to make change in a BIG way

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

A complete Guide on UiPath Orchestrator

Quantum Journey 2: I’m not on Dugs

Kafka Connect at GumGum — Background and Motivation

Citizen Developer: From Pariah to Superhero

Helper Methods: They’re here to help!

Being a principal engineer at Skyscanner

DOGECOIN MINING: HOW TO MINE DOGECOIN

Deploy Serverless Docker Containers and Functions with Koyeb CLI

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sairam Penjarla

Sairam Penjarla

Looking for my next opportunity to make change in a BIG way

More from Medium

Blockchain in a nutshell and all its key terms!

“Lead Self!!”

How can efficient collaboration tools reduce costly food wastage in supply chains?

kalycoin project