# [LeetCode] 53. Maximum Subarray (Medium)

###### tags: `LeetCode`

## 題目
給定一個array`nums`，找出加起來最大的連續subarray，回傳那個和。

## 限制條件
* `1 <= nums.length <= 10^5`
* `-10^4 <= nums[i] <= 10^4`

## 範例
* Example 1:

    輸入: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    輸出: 6

* Example 2:

    輸入: nums = [1]
    輸出: 1

* Example 3:

    輸入: nums = [5, 4, -1, 7, 8]
    輸出: 23

## 解答
### Kadane 演算法
Kadane 演算法是一種類似動態規劃的做法。這個做法對array的所有元素掃描一次，在每個點上計算以該點做為結尾的最大subarray和。這個subarray由兩部分組成：以前一個位置為結尾的最大subarray、該位置的數值。由於以每個位置做為結尾的最大subarray都是基於其前一位置的最大subarray計算得出，因此這個做法滿足optimal substructure（最佳子結構），因此可看成動態規劃的一個例子。

那麼我們要怎麼以前一個位置的最大subarray和來計算出目前位置的最大subarray和呢？很簡單，如果前一個位置的最大subarray和大於0，就把目前的元素加進去；否則，新的最大subarray和就只包含目前的這個元素。然後，我們再保留目前為止看到的和裡面最大的和即可。

為了加快執行速度，我們也考慮2個最簡單的base case：當`nums`長度為1時，回傳那個唯一的元素；當`nums`長度為2時，我們回傳兩個元素本身還有兩個元素相加這三種可能的最大的那個。

我們的Python code實作如下：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) > 2:
            s = 0
            max_s = - float("inf")
            
            for i in range(len(nums)):
                if s >= 0:
                    s += nums[i]
                else:
                    s = nums[i]         
                max_s = max(s, max_s)
            return max_s

        else:
            if len(nums) == 2:
                return max(nums[0], nums[1], nums[0] + nums[1])
            if len(nums) == 1:
                return nums[0]        

在這邊，`s`即為以目前元素做為結尾的最大subarray和，而`max_s`則是用來保留目前為止看到的最大subarray和。

Kadane演算法的時間複雜度可以很容易看出來是 $O(n)$，因為只有一個for迴圈，而裡面的所有步驟只需要常數時間。空間複雜度的部分，我們只用了2個參數（`s`和`max_s`），因此是 $O(1)$。可以看出，Kadane演算法是個很有效率的演算法。

### Divide and conquer
既然滿足optimal substructure，那代表其實我們也可以使用divide and conquer（分治法）的方式來寫出一個遞迴解。這個方法雖然比Kadane演算法沒效率一些，但仍有其討論價值。

Divided and conquer方式的核心就是把問題分解成較小的子問題，分別解決這些子問題，再透過結合這些子問題的解來獲得原問題的解。

對於這個問題，要怎麼把原問題分解成較小的子問題呢？我們可以把題目給定的`nums` array 切成左右兩半。這樣一來，相加起來最大的subarray可以有三種可能性：
1. 全部都在左半邊
2. 全部都在右半邊
3. 橫跨左右兩半

我們只要取這三種可能性中最大的結果，就會是最後的答案。前兩個case很簡單，只要使用遞迴方式求解就可以了。比較麻煩的是最後一個橫跨兩半的case。

要找到橫跨兩半的最大subarray也不難，只要分別找出包含交接點左右兩邊元素的subarray中最大的subarray，再把兩邊的subarray接起來即可：
以上就是使用divide and conquer解決這題的邏輯，剩下的工作就是把這些邏輯寫成Python code：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def helper(l, r):
            if l > r:
                return - float("inf")
            
            m = int((l + r) / 2)
            
            curr = best_left = best_right = 0
            
            for i in range(m - 1, l - 1, -1):
                curr += nums[i]
                best_left = max(best_left, curr)
                
            curr = 0
            
            for i in range(m + 1, r + 1):
                curr += nums[i]
                best_right = max(best_right, curr)
                
            best_comb = best_left + best_right + nums[m]
            
            left_half = helper(l, m - 1)
            right_half = helper(m + 1, r)      
            
            return max(left_half, right_half, best_comb)
        
        return helper(0, len(nums) - 1)

在這邊我們定義一個`helper` function來實作遞迴的部分，這個function吃兩個參數：`l`和`r`，分別指示目前要尋找`nums` array部分的左邊界和右邊界。

這個演算法的時間複雜度是$O(n \log n)$，因為總共有$O(\log n)$次呼叫，每次都有一個$O(n)$的for迴圈。空間複雜度是$O(\log n)$，因為有$O(\log n)$個結果要儲存，每個佔用$O(1)$的空間。