【LeetCode 簡單題】11-最大子序和

聲明：

今天是第11道題。給定一個整數數組 

nums

 ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。以下所有代碼經過樓主驗證都能在LeetCode上執行成功，代碼也是借鑒别人的，在文末會附上參考的部落格連結，如果侵犯了部落客的相關權益，請聯系我删除

（手動比心ღ( ´･ᴗ･` )）

啊啊啊啊這篇博文整整寫了1個上午啊，保持專注的話1個半小時應該就夠，慢慢來吧~~~~~~

正文

題目：給定一個整數數組 

nums

 ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
           

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

解法1。周遊整個數組，數之和用sum記錄，最大和用max記錄，初始值分别為0，nums[0]。如果sum累加目前元素>=0，則選擇累加（此元素小于0的話，max就不更新，是以max能保證無論sum怎麼加，max都記錄的是sum曆史最大值），如果sum累加目前元素<0，則令sum置0，同時比較目前元素和max大小來選擇是否更新max

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # V 1.0，能送出
        sum = 0
        max = nums[0]
        for num in nums:
            if sum + num >= 0:
                sum += num
                if sum > max:
                    max = sum
            else:
                sum = 0
                if num > max:    # 這一步并不是多餘的，試想如果nums全負的話，這裡可以用max擷取到數組的最大值
                    max = num
        return max
           

 解法2。比解法1更耗費時間，窮舉了所有可能性并存儲起來，能運作正确，但送出逾時，基本思路就是2個循環嵌套，每輪把所有加和情況放到數組sums中，計算出1個最大值，下一輪出現更大的就更新。

class Solution:
    def maxSubArray(self, nums):
        i = 0
        result = nums[0]
        len_nums = len(nums)
        # 用2個循環嵌套，窮舉所有加和可能性放在sums裡，每一個外層循環中比較出當次的最大值存到result，下一輪如果存在更大的和就更新result，但是非常耗時
        while i < len_nums:
            temp = 0
            sums = []
            for j in range(i,len_nums):
                temp += nums[j]
                sums.append(temp)
            if result < max(sums):
                result = max(sums)
            i += 1
        return result
           

解法3。 分而治之思想。把輸入數組分為左、右兩邊，最長子序列有3種情況，1-在左邊，2-在右邊，3-左右通過中間元素相連，1和2的實作通過遞歸調用divide函數求取所有可能情況的最大值，3通過從中間元素的兩邊開始計算和，把最大值記錄在*_border_max中。具體實作如下

class Solution:
    def divide(self,nums,left,right):
        if left > right:
            return -2147483647
        mid = int((left+right)/2)

        # 情況3-從中間往左一位開始求左邊的最大值，考慮和中間元素相連
        sum = 0
        left_border_max = 0
        for i in range(mid-1,left-1,-1):
            sum += nums[i]
            left_border_max = max(left_border_max, sum)

        # 情況3-從中間往右一位開始求右邊的最大值，考慮和中間元素相連
        sum = 0
        right_border_max = 0
        for i in range(mid+1,right+1):
            sum += nums[i]
            right_border_max = max(right_border_max, sum)
        
        # 情況1、2-求左、右兩邊的最大值，不考慮和中間元素相連
        left_max = self.divide(nums,left,mid-1)
        right_max = self.divide(nums,mid+1,right)

        # 傳回3種情況的最大值
        return max(left_border_max+nums[mid]+right_border_max,max(left_max,right_max))

    def maxSubArray(self, nums):
        # 調用求最長子序列的函數
        return self.divide(nums,0,len(nums)-1)
           

結尾

解法1：https://blog.csdn.net/u012860582/article/details/80483102

解法2：https://blog.csdn.net/qq_34364995/article/details/80284270

解法3：https://blog.csdn.net/qqxx6661/article/details/78167981