[leetcode][C][python] 53. Maximum Subarray

這題雖然是easy, 但是還是卡了一下，一開始雖然想到大致上O(n)的做法，但是沒有想得很透徹，寫了一堆例外處理卻一直有處理不完的case
後來重新整理一下思緒，終於將架構改得比較完整




題目要求是在一個array 中找出總和最大的sub array，暴力法當然就是依序選所有可能的subarray的頭(n)、計算出從這個頭開始到後續各個element的總和((n-1)!)，最後取最大值
，這樣複雜度會達到O(n*(n-1)!)


我的作法是allocate一個存放summary的array，大小與輸入相同，之後只要將其跑過一輪即可求解，因此時間複雜度與空間複雜度都是O(n)

概念大概如下:

1. 一開始想像輸入的資料像是每日股價漲跌，我們要做一個累加的array，這就像是每日漲跌畫出來的線形圖(時間複雜度與空間複雜度都是O(n))
1. 在線型圖上任兩點的差距即為對應的subarray 加總數值
2. 因此我們的目標是找出線形圖上由左至右的最大差距(若不幸線形圖一路下滑，還是一樣的道理，最大=下滑最少)
2. 在存放summary的array上依序跑(時間複雜度是O(n)，空間複雜度是O(1))
1. 建立base變數，存放目前為止線形圖的最低點
1. 想像右邊有一高點，則最大差距應為此高點與其左方最低點的差距
2. 
   
2. 建立max 變數，存放跑到目前為止，線形圖上的點與當下base間的差距最大的一組值(即為subarray 最大總和)

source code:
https://github.com/cy-arduino/leetcode/blob/master/53.%20Maximum%20Subarray.c
https://github.com/cy-arduino/leetcode/blob/master/53.%20Maximum%20Subarray.py