LeetCode 0053. Maximum Subarray最大子序和【Easy】【Python】【動(dòng)態(tài)規(guī)劃】

Problem

LeetCode

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

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

問題

力扣

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:

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

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

思路

動(dòng)態(tài)規(guī)劃

找到 dp 遞推公式。dp 等于每個(gè)位置的數(shù)字加上前面的 dp，當(dāng)前面的 dp 是負(fù)數(shù)時(shí)就不要加了。

時(shí)間復(fù)雜度: O(len(nums))
空間復(fù)雜度: O(1)

Python代碼

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        dp = 0
        sum = -0xFFFFFFFF
        for i in range(len(nums)):
            dp = nums[i] + (dp if dp > 0 else 0)  # if dp > 0: dp = nums[i] + dp, else: dp = nums[i]
            sum = max(sum, dp)
        return sum

代碼地址

GitHub鏈接