Kadane’s Algorithm

Kadane’s Algorithm

Hello Amigos , what if I ask you to find the maximum sub array in an array .

Let’s consider this array for example

You have to find maximum sub array here.

What will be your approach? How will you find it?

Before proceeding further, once try to solve it by yourself.

Okay Done? whatever be your approach, your all queries will get resolved here.

First of all, let us understand what is “subarray “.

A subarray is a (contiguous part of an array ). Let’s take an example

So if I ask you to find all subsequence or all subarrays of this array then what would be they?

They are (3),(3,4),(3,4,7),(3,4,7,2),(3,4,7,2,5),(4),(4,7),(4,7,2),(4,7,2,5),(7),(7,2),(7,2,5),(2),(2,5),(5)

So there are 15 possibilities of the subsequence or subarrays. For an array /string of size n, there are “n*(n+1)/2” subarrays.

Eg. Here n=5 ,so 5*(5+1)/2=15

Note-: Here you should take care of the” sequence” from left to right

eg. (3,5),(4,2),(3,2,5) etc. is not a subarray , as there is no sequence.

Okay now we are clear with the prerequisite that is subarray.

So , How do we find out maximum sub array .

Naïve approach says that finding all subarrays and then calculating their sum side by side. Then find out maximum sum, corresponding to that maximum sum is the maximum subarray.

This approach takes O(n²) of time complexity. So we need some better approach to find out maximum subarray.

Kadane’s Algorithm flips the complexity to find out the maximum subarray from O(n²) to O(n). Curious !

Lets Break the Algorithm !

Consider an array.

— — — — — — — — — ->

(consider this as a train starting from inidex0)

Commencing from index 0 which is 4 , we will add 3 the -2 and so on, but we have to follow some conditions.

The trick is we are adding linearly. When the sum become “negative” ,the current_sum become zero and start again.

The maximum subarray here is (4,5,9,-3,4,7)

Steps-:

1. At index 0 it is 4 , so current _ sum is 4 and overall_sum is also 4 . Overall_sum is the largest sum with respect to current_sum.

2. On index 1 it is 3, so sum is 7 and we continue process till we get sum as -2 , when we get -2 , we get 2 choices

a. Either Adding -2 to 4 we get 2 or we can start a new train from 4, which is much beneficial.

Let’s examine other example

The maximum subarray is (4,-3,10.-5,67,9,9)

Thank you for visiting to my blog. I always believe in power of community. I have been learning a lot from the community , now its time to give back to the community . Stay update with my profile , So much will come related to DSA.

For connecting me , visit this Linkedin Profile-:https://www.linkedin.com/in/utkarsh-rastogi-0138761a9

--

--

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