LeetCode Maximum Subarray

LeetCode解題之Maximum Subarray

原題

求一個數組中和最大的子數組。

注意點：

例子：

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

輸出: 6(數組[4, -1, 2, 1]的和)

解題思路

又是比較經典的動態規劃的題目。主要有以下幾個概念，依次計算以第k個數作為子數組末尾的最優子數組（和最大）的和dp[]，然後求dp中的最大值。那遞推關系是怎樣的呢，當把下一個數字num[k+1]最為末尾數字時，要看它之前與它相連的子數組的和是否是正的，如果是正的，應該加上，否則捨棄。下面的代碼把求dp和求dp中的最大值一起計算了，所以沒有額外的數組dp。

現在還有一個疑問，就是num[k+1]之前與它相連的子數組應該定義為多長，它的起始位置是最靠近它的滿足與這個數字相連的子數組的和為負的數字。如[-2, 1, -3, 4, -1, 2, 1, -5, 4]中-3前子數組的開端是1，-1是4，-5也是4。

AC源碼

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        current = nums[0]
        m = current
        for i in range(1, length):
            if current < 0:
                current = 0
            current += nums[i]
            m = max(current, m)
        return m


if __name__ == "__main__":
    assert Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6