LeetCode Maximum Subarray

最基本DP

def maxSubArray(self, nums):
        output = [nums[0]]
        for i in range(1,len(nums)):
            output.append( max(output[i-1]+nums[i],nums[i]) )
        return max(output)

 

优化：用变量代替数组

def maxSubArray(self, nums):
        t, rtn = nums[0], nums[0]
        for i in range(1, len(nums)):
            t = max(t+nums[i], nums[i])
            rtn = max(rtn, t)
        return rtn

刷题防身 python DP array leetcode Maximum Subarray Comments(2) 2015年7月17日 17:03