LeetCode 0053. Maximum Subarray最大子序和【Easy】【Python】【動態(tài)規(guī)劃】
Problem
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.
問題
給定一個整數(shù)數(shù)組 nums 喧务，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
進階:
如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解崖咨。
思路
動態(tài)規(guī)劃
找到 dp 遞推公式。dp 等于每個位置的數(shù)字加上前面的 dp晴弃，當前面的 dp 是負數(shù)時就不要加了掩幢。
時間復雜度: O(len(nums))
空間復雜度: 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
