Maximum Subarray

Problem: Maximum Subarray

We can use dynamic programming to solve this problem. Every time we get a new number, we can decide to start a new subarray from current number or add current number to previous subarray to achieve maximum sum.

Code in Python:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return
        dp = [nums[0]]
        for num in nums[1:]:
            dp.append(max(num, dp[-1]+num))
        return max(dp)