python solution DP


  • 0
    1. fn(ary)= max( fn(ary[:mid]),fn(ary[mid+1:]) , cn(mid) )
    	cn: crossSum:
    
    class Solution(object):
    	def maxSubArray(self, nums):
    		"""
    		:type nums: List[int]
    		:rtype: int
    		"""
    
    		cV=[0]*len(nums)
    
    		maxV=0
    
    		for idx,v in  enumerate(nums):
    
    			if idx==0:
    				cV[idx]=v
    				maxV=v
    			else:
    				cV[idx]=max(nums[idx-1],cV[idx-1])+nums[idx]
    				maxV=max(v,cV[idx],maxV)
    
    		return maxV
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.