Save that RAM!

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/)

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)

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)

Code : Karp-Rabin