Week3; Maximum Sub Array
This is the first algorithm I learnt well from Introduction to Algorithms; CLRS book. It took me days to finally figure out how it works. Believe me, I was very happy when I got it. That feeling is what I love. It’s the only feeling that keeps me alive.
Maximum subarray problem is to find the sub array which sum is the maximum. e.g.,
arr = [1, 2, 3, 4]
Which sub array produces max sum?
I am kidding. It’s the array itself because it’s all positive.
arr = [2, -1, 5, -9]
The answer is [2, -1, 5] which add up to 6.
arr = [2, -1, 5, 9, -22, 15, 3, -2, 22, -17, 9, 8, 7, -5]
I don’t know. I just typed random numbers.
There are more than one way to find the maximum sub array. One approach is using iteration. Brute-forcing all possibilities which is fun if you can figure it out yourself.
I am writing about Divide and Conquer algorithm.
One simple concept to understand is it lies somewhere in the array. I had a hard time before I knew it. Read below the trick.
arr = [2, -1, 5, -9, 3, -2]
First, imagine you divide the array from middle. You get two subarrays.
[2, -1, 5] & [-9, 3, -2]. The maximum sub-array must be in left or right.
NO, you know something is not right? What about the middle part.
What if it lies in the crossing part in middle?
So, let’s find from middle, between 5 & -9. Think it of as the bridge crossing the river. Construct left side, right side and join. Find out how large your sum can be if you go to left from middle and if you go to right from middle.
5, -1 sum=4
5, -1, 2 sum=6
-9, 3 sum=-6
-9, 3, -2 sum=-8
LEFT is maxSum = 6, Right is maxSum = -6
Then, save it. [2, -1, 5, -9, 3] is maximum crossing sub array.
Calculate for pure left side and pure right side. I mean not to confuse with crossing left, right.
[2, -1, 5] & [-9, 3, -2].
WE DO IT RECURSIVELY.
I am just introducing you. It’s your duty to go into it deeper if you want to understand. Here are resources.
You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous…www.geeksforgeeks.org
Draw and run the algorithm with book and pencil. It really helps!!
Read the book if you can. CLRS.
Disclaimer: I am not writing technical lessons so I am not explaining it in details. May contain FALSE INFO. Go to credible resources. I am giving you just introduction to the concept.