53.md

53 Maximum Subarray

Description

link

---

General Type

Local and Total Variable Dynamic Programming

---

Solution

• Sum : total maximum number

• Cur : maximum number conclude current number

• update two vars (Cur = max(Cur + nums[i],nums[i]))

---

Code

Complexity T : O(n)

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