Dynamic Programming -- Maximum subarray problem

WIKI: http://en.wikipedia.org/wiki/Maximum_subarray_problem



仔細想想 Kadane's algorithm 為什麼正確？為什麼 T(n) = O(n)

如果將 array 1D 維度推廣到 matrix 2D 維度，

可以將問題化成 O(n^2) 個 maximum subarray problems，

因此 T(n) = O(n^3)。

UVa 108: http://uva.onlinejudge.org/external/1/108.html

Solution: https://bitbucket.org/Menggen/uva/src/4180a681695afa0f56a090be62dc8637a27a04d0/UVa/acm_108.cc?at=master