Maximum Subarray Sum

题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

解题方法

brute force

O(n^2)

DP

local[i]表示包含当前index为i的值的最大sum global[i]表示在index为i的之前的最大sum（不一定包含i）

no dp

其实可以不用DP， 只用一个variable保存当前的最大值，如果小于0，那么在下一个 element那里就可以舍去之前的

Solution

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        localDP = [-sys.maxint for i in range(length)]
        globalDP = [-sys.maxint for i in range(length)]

        localDP[0] = nums[0]
        globalDP[0] = nums[0]
        result = nums[0]

        for i in range(1, length):
            localDP[i] = max(localDP[i-1] + nums[i], nums[i])
            globalDP[i] = max(localDP[i], globalDP[i-1])
            if globalDP[i] > result:
                result = globalDP[i]

        return result

Reference