Save that RAM!

[savethatram]

Maximum Subarray problem - Kandane Algorithm

Find the subarray with the maximum sum. Can be solved with Dynamic Programming. The solution presented here does not use DP. Links: [Wikipedia](http://en.wikipedia.org/wiki/Maximum_subarray_problem), [Stackoverflow](http://stackoverflow.com/questions/7943903/maximum-subarray-of-an-array-with-integers), [Slides](http://rerun.me/blog/2012/08/30/maximum-continuous-subarray-problem-kandanes-algorithm/)

[savethatram]

Find the k-th largest element in an array (Hoare's selection algorithm)

Naive solution: Sort the array in descending order, using either of the O(nlogn) complexity algorithms (Merge Sort, Quick Sort). Return arr[k] Solution without sorting 1. Build a Max-heap and pop k times to get the k-th largest element. Complexity: O(n) + O(k * logn) = O(n) if k is small. Link: [Joel On Software](http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17), [StackOverflow](http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on?rq=1) 2. QuickSelect: modification over QuickSort - Hoare's selection algorithm Link: [QuickSelect](http://pine.cs.yale.edu/pinewiki/QuickSelect) Code: [QuickSelect](https://github.com/angad/py-algorithms/blob/master/Algorithms/quickselect.py)

[savethatram]

Boyer and Moore's Linear Time majority vote algorithm

This algorithm is used to determine the majority element in an array i.e. the element that occurs more than half the number of times the length of the array. In other words, more than half of the entries in the array are equal to N, for some integer N. This algorithm can find the number N with a single pass over the array. Link: [Moore's description](http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html), [StackOverlfow](http://stackoverflow.com/questions/278488/puzzle-find-the-most-common-entry-in-an-array)

[savethatram]

Karp Rabin Algorithm

Karp Rabin is an efficient string search algorithm that uses Rolling Hashing.

Wikipedia : Rolling Hash Karp Rabin

External Links : MIT CS6.006 Lecture 6

Code : Karp-Rabin