【LeetCode】53. 最大子序列

問題描述

Given an integer array 

nums

, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

給定一個整數數組編号，找到具有最大和的連續子數組(至少包含一個數字)并傳回其和。

如果您已經找到了O(n)的解決方案，那麼嘗試使用分治方法編寫另一個解決方案，這種方法更加微妙。

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
期待結果: [4,-1,2,1] 存在最大和為 6.
           

Python 實作

實作一：依次記錄周遊到數組目前位置時得到的相對最大和。

這裡的相對是指，目前值與加上目前值後的結果兩者之間的較大值。該算法不考慮數值的具體特征，隻記錄周遊過程中子序列的和的結果。每當出現一個值，比上一個子序列所有值的總和還要大，那麼從該值重新開始一個子序列。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        maxSum = [nums[0]]
        for i in range(1, len(nums)):
            maxSum.append(max(nums[i], nums[i] + maxSum[i-1]))
        return max(maxSum)
           

實作二：分而治之

基本思路就是從中間将數組分開，從中間開始分别往兩個方向去計算最大和，取兩者較大值或者兩者之和。

這裡需要注意的是，求和的時候不再像上面那樣找間斷的子序列，而是從起點開始，依次加上新的值得到新的結果。這樣子才能保證當我們取兩者之和時，得到的結果依然是一個連續子序列求和的結果。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # Basis condition.
        if len(nums) < 2:
            return nums[0]
        
        maxSum = leftSum = rightSum = float('-inf')
        l = r = 0
        
        # Start from the middle to right.
        for i in range(len(nums)//2, len(nums)):
            r += nums[i]
            rightSum = r if r > rightSum else rightSum
            
        # Start from the middle to left.
        for i in range(len(nums)//2-1, -1, -1):
            l += nums[i]
            leftSum = l if l > leftSum else leftSum
            
        # Connect the result between two parts.
        total = leftSum + rightSum
        
        return max(total, self.maxSubArray(nums[ : len(nums)//2]), self.maxSubArray(nums[len(nums)//2 : ]))
           

連結：https://leetcode.com/problems/maximum-subarray/