• 分類：DP

• 考察知識點：Divide+Conquer/DP/Greedy

• 最優(yōu)解時間復雜度：O(n)DP/Greedy/Divide+Conquer不知道咋做

• 最優(yōu)解空間復雜度：O(1)

53. Maximum Subarray

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.

代碼：

Greedy方法:

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #邊界條件
        if len(nums)==0:
            return -1
        
        sum_=nums[0]
        res=nums[0]
        
        for i in range(1,len(nums)):
            sum_=max(nums[i]+sum_,nums[i])
            res=max(res,sum_)
        
        return res

DP方法:

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #邊界條件
        if len(nums)==0:
            return -1
        
        dp=[float("-inf")]*len(nums)
        dp[0]=nums[0]
        res=nums[0]
        
        for i in range(1,len(nums)):
            dp[i]=max(dp[i-1]+nums[i],nums[i])
            res=max(res,dp[i])
        
        return res

討論：

1.這道題的Greedy算法是DP的變種
2.這道題的follow up有一個Divide and Conquer的算法，不知道要咋搞，很煩，很方，很藍瘦TAT

人不裝X還有什么意義！