Yes. It's been a long time. But some times we just need to return to the beginning to remember what we forgot. Ah, well, the blog was started when I joined college, it is kinda poetic that I should re-begin it considering I am at the very last league of the Great Indian Rat-Race.
What got me back, well that includes Rupal's constant request to write something, me exhausting my Hard Disk for good movies to watch and a constant boredom that has prevailed over me these past few days.
Ok Let's talk about what this post is about- "Kadane's Algorithm"
It's an algorithm to find the maximal sub array for a given array. Maximal Sub array means that a sub set of an array which has the maximum sum.
The Algo works in linear time, i.e. O(n). Which basically boils down to saying that we just have to traverse the array only once.
Kadane's is such a simple approach to the most common array problem.
Let A[0 ... n-1] be an array of integers, we find the current sum till each element in the array starting from the left and going till the end and we keep on comparing it with a maximum sum so as to change the maximum sum when the current sum exceeds it.
This is a the most simple Dynamic Programming problem.
Note: It will return 0 when array consists of all negative numbers.
Also why write about this ? Well that is cause I found it too beautiful. The simplicity of it amazed me and I wanted to share this piece of information.
