Maximum_subarray_problem

leetcode上的題目：Best Time to Buy and Sell Stock

問題很簡單，隻不過想總結一下其中經典的一些解法。

有不同的O(n)時間複雜度的解法，比如周遊i=[0, n)，每次計算nums[i]與[0, i]之間的最小值的差，更新全局最大值。代碼如下：

方法一：

// time: O(n),  space: O(1)

int minv = INT_MAX;

int gmax = INT_MIN;

for (int i = 0; i < n; ++i) {

minv = min(nums[i], minv);

gmax = max(gmax, nums[i] - minv);

}

return gmax;

該題也可以轉化為一個經典的問題：求一個數組的子數組最大和。

記diff[i] = nums[i] - nums[i - 1]

則 nums[i] - nums[j] = diff[i] + diff[i - 1] + ... + diff[j+1], 是以問題轉化為求diff數組的子數組最大和。該問題有一些經典的解法：

方法二：

分支界定，時間複雜度為O(nlog(n))。

把數組A[1..n]分成兩個相等大小的塊：A[1..n/2]和A[n/2+1..n]，最大的子數組隻可能出現在三種情況：

    A[1..n]的最大子數組和A[1..n/2]最大子數組相同；

    A[1..n]的最大子數組和A[n/2+1..n]最大子數組相同；

    A[1..n]的最大子數組跨過A[1..n/2]和A[n/2+1..n]

前兩種情況的求法和整體的求法是一樣的，是以遞歸求得。

第三種，我們可以采取的方法也比較簡單，沿着第n/2向左搜尋，直到左邊界，找到最大的和maxleft，以及沿着第n/2+1向右搜尋找到最大和maxright，那麼總的最大和就是maxleft+maxright。

而數組A的最大子數組和就是這三種情況中最大的一個。

方法三：

動态規劃：time:O(n)

如果用函數f(i)表示以第i個數字結尾的子數組的最大和，那麼我們需要求出max(f[0...n])。我們可以給出如下遞歸公式求f(i)

這個公式的意義：

1. 當以第(i-1)個數字為結尾的子數組中所有數字的和f(i-1)小于0時，如果把這個負數和第i個數相加，得到的結果反而不第i個數本身還要小，是以這種情況下最大子數組和是第i個數本身。
2. 如果以第(i-1)個數字為結尾的子數組中所有數字的和f(i-1)大于0，與第i個數累加就得到了以第i個數結尾的子數組中所有數字的和。

方法四： Kadane's algorithm， time:O(n), space:O(1)

int max_ending_here = 0, max_so_far = 0;
for (auto x : nums) { 
    max_ending_here = max(0, max_ending_here + x);
    max_so_far = max(max_so_far, max_ending_here);
}      

參考資料： http://www.cnblogs.com/xkfz007/archive/2012/05/17/2506299.html

http://www.cnblogs.com/xwdreamer/archive/2012/05/04/2482507.html

https://en.wikipedia.org/wiki/Maximum_subarray_problem