Introduction

Hello DSA aspirants I am here with another blog on something new I guess, the reason behind this is the first blog mine on algorithms. Yes, is very hard to understand the algorithm on video but in the form of a blog or article, it is even more difficult. I am pretty sure that my blog is enough to understand this algorithm so, make sure you read till the end. I take real-world examples to make it as simple as possible.

Why?

Before getting into the details of the algorithm just answer this question

Why this algorithm?

In my case, I came to know about this algorithm because of the maximum subarray sum problem on the leetcode. I came across a lot of YT videos but everyone solving the problem the way it is and no one is telling what was happening behind the scenes this is also one of the reasons why I started writing this blog.

By googling I found this--> Kadane's Algorithm is an iterative dynamic programming algorithm. It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position. It is good but not so clear. So, let's dive into the actual thing!!! So, let's understand the word maximum subarray sum by breaking it down.

The backbone

Subarray

After watching those many videos and reading articles one thing that revolves around the algorithm is Subarray. Let's try to understand what is a subarray means. Well, it is a small portion or small part in the array with contiguity.

Note: Sometimes the entire array may be subarray depending on the condition.

Consider an array with a small length and write all the possible combinations of the subarrays!!

nums = [1, 2, 3, 4, 5]

1                  2                  3                  4                5
1 2                2 3                3 4                4 5 
1 2 3              2 3 4              3 4 5               
1 2 3 4            2 3 4 5            
1 2 3 4 5

The possible ways

If you observe the combinations carefully every element in the array has maximum 2 possibilities they are

1. Either it can start a new subarray.

2. Or it is a part of any subarray.

Let's try to understand even more clearly. pick the "3 4" combination and try to implement the possibilities in that.

I think it making some sense right!!

Subarray Sum

As the name indicates subarray sum we have to do the addition operation on all the individual elements in that particular subarray.

Maximum Subarray Sum

Here is the interesting and favorite part i.e., in that whole combinations we have to pick that one particular subarray whole sum is maximum when compared to the rest of the subarray. At first, I thought it was easy peasy !!!! We can just take a new array place all the combination sum and return the maximum element in that.

But guys if we think like this in the first attempt itself we are hit by our well-known friend TLE because for large arrays it is the completely unmatured solution ever. Here is our time-saving and pretty much savvier came in to picture The Kadane's Algorithm

Business Deal

Let's understand this algorithm using some business terms like investment, partnership

Consider an array with both negative and non-negative integers

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Assume every element as a person want to start a business as it is business "partners" play an important role in the process right like either we get most of the profit or we get into losses. The same thing happened here also it is more clear if we try to understand this in the form of tracks and consider 2 variables to keep the track of current_maximum and orginal_maximum.

let's start with -2 just make a general assumption that we only do business if we have money right? -2 indicating that he has a dept of ₹2 then how can he even start a business so, it is out of the scope to move to the next person?

person "1" has 2 choices either he has to start his own business or he can partner with the previous person . in the second case if he did that he end up with -1 means loss so, it is better to start his own business at least better than the loss and he started his own business (TRACK-1).

note: Remember we are keeping the track of the maximum_sum in every decision

This track thing keeps on going until we get the negative sum (indicating the loss). We moved to the next person "-3" obviously I told you initially about the choices he has to start his own business or partner with the previous person. In both cases, we are ending up with a negative sum so we just move to the next person and so far we have maximum_sum as only "1" in the (TRACK-1)

person "4" also has 2 choices either start or mingle, if he mingles with the previous person ending up with ₹1 as the sum even though it is positive on the other hand if he starts on his own he has ₹4 which is better than the mingle. So, he decided to his own business(TRACK-2)

Note: starting his business nothing but another TRACK

This track thing keeps on continuing until we get negative as a sum.

As we find the key behind this start doing the same thing for the remaining elements also

---

"-1"

own-business---> Not possible

if mingle with "4" ---> end up with "3"(better than the own start)so, start mingle

---

"2"

own-business---> possible but try to check if he is getting more profit on mingle or not

if mingle with "3" ---> end up with "5"(better than the own start)so, start mingle

---

"1"

own-business---> possible but try to check if he is getting more profit on mingle or not

if mingle with "5" ---> end up with "6"(better than the own start)so, start mingle

---

"-5"

own-business---> Not possible

if mingle with "6" ---> end up with "1"(better than the own start)so, start mingle

---

"4"

own-business---> possible but try to check if he is getting more profit on mingle or not

if mingle with "1" ---> end up with "5"(better than the own start)so, start mingle

---

So that's it we reach the end and by using one for loop we are getting the maximum subarray sum. This is the basic idea behind this algorithm it was even clear if we look at this in the form of code

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
original_max = nums[0]  #assinging the first element as max_element
current_max = 0
for n in nums:
    if current_max > 0: #keeping on parnering until we get the negeative sum
        current_max +=n
    else:
        current_max = n      #own business(TRACKING)
    original_max = max(original_max, current_max)  #Keeping the maximum_subarray_sum
print(original_max)

In the above code snippet, both the variables original_max and current_max play a major role in which subarray gives the maximum sum as output.

Conclusion

That's pretty much about Kadane's algorithms, Hope you understand I tried my level best to make things as uncomplicated as possible. if you find it useful and if you learned something new DO try to share, let me know your thoughts below and feel free to reach out to me if any issues.

Let's connect to grow together !!!!

Twitter ---> Malavi Pande

LinkedIn --->Malavi Pande