Maximum Subarray Problem

Maximum subarray is a typical interview question you may face. Its description can be found here.

There are two common approaches to solve this problem, dynamic programing($O(n)$) and divide and conquer($O(n\,log\,n)$). I am going to share the solutions and thoughts of them in this article.