Chat

If you have seen interview questions like find the maximum sum in an array using any contiguous sub-arrays in it then you should read further.

We have discussed a few dynamic programming questions on this website. This post talks about yet another one (arguably). Let’s take an example – in the array {-2, -3, 4, -1, -2, 1, 5, -3}, what is the maximum sum that you can obtain by summing up any contiguous elements in it? Well, you can compare each element one by one and build an O(n*n) solution to do that. But can we do better? Let’s see what Mr. Kadane proposed.

For every i, let’s try to calculate the maximum sum possible till that i.

Array = {-2, -3, 4, -1, -2, 1, 5, -3}; i will go from 0 to 7. Let’s keep two variables:
sum_at_i = 0
max_sum = 0

At i = 0;
sum_at_i = sum_at_i + array[i] = -2
Since sum_at_i < 0, we re-initialize:
sum_at_i = 0
max_sum = 0

At i = 1;
sum_at_i = sum_at_i + array[i] = -3
Since sum_at_i < 0, we re-initialize:
sum_at_i = 0
max_sum = 0

At i = 2;
sum_at_i = sum_at_i + array[i] = 4
Since sum_at_i > 0 and sum_at_i > max_sum; we make:
sum_at_i = 4
max_sum = 4

At i = 3;
sum_at_i = sum_at_i + array[i] = 4 – 1 = 3
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 3
max_sum = 4

At i = 4;
sum_at_i = sum_at_i + array[i] = 3 – 2 = 1
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 1
max_sum = 4

At i = 5;
sum_at_i = sum_at_i + array[i] = 1 + 1 = 2
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 2
max_sum = 4

At i = 6;
sum_at_i = sum_at_i + array[i] = 2 + 5 = 7
Since sum_at_i > 0 and sum_at_i > max_sum; we make:
sum_at_i = 7
max_sum = 7

At i = 7;
sum_at_i = sum_at_i + array[i] = 7 – 3 = 4
Since sum_at_i > 0 but sum_at_i < max_sum; we don’t change max_sum:
sum_at_i = 4
max_sum = 7

And there we go! Our answer is 7. (But can you also find the indices of the sub-array?)

You can find the corresponding C++ code for the above algorithm HERE.

Now that you have found the maximum sum, can you also find the minimum sum? Give it a try.

References:

1. GeeksforGeeks 2017. “Largest Sum Contiguous Subarray”. https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/. [Online; accessed 27-March-2018].
2. Kartik Kukreja 2013. “Everything Under The Sun”. https://kartikkukreja.wordpress.com/2013/06/17/kadanes-algorithm/. [Online; accessed 27-March-2018].

# How to Control Your Emotions During a Difficult Conversation

Chat

Today I read an article on how to maintain your composure and keep calm while being in an argument. With whatever little experience I have, I have seen people lose their cool more often than not, which actually comes back to bite them in their arse later.

Have a read in free time and see if it helps you. I think no matter where you are in your career or personal life, you can learn a few things from the article. It won’t take more than 5-6 minutes to read the entire piece – LINK.

# All I need is…

Chat

Maybe I am emotional in the moment, but this song is pretty powerful. And while I think different people can infer and relate different things with this song, I can relate something as well…

# I won’t back down

Chat

There are some songs that you instantly connect with, that pump you up, that makes you have goosebumps. But I also think that the effect of a song on any person depends largely on the mood or the circumstance they are in or going through. Anyway, while watching Grey’s Anatomy (I think season 8, last episode), I found one such song.