[DP/Greedy]053 Maximum Subarray

• 分类：DP

• 考察知识点：Divide+Conquer/DP/Greedy

• 最优解时间复杂度：O(n)DP/Greedy/Divide+Conquer不知道咋做

• 最优解空间复杂度：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还有什么意义！