O(n) dp python solution


  • 0
    H
    class Solution(object):
    def maxSubArray(self, nums):
        if len(nums)>0:
            ans=[]
            ans.append(nums[0])
            for i in range(len(nums)):
                if i==0:
                    continue
                if nums[i]+ans[i-1]>nums[i]:
                    ans.append(nums[i]+ans[i-1])
                else:
                    ans.append(nums[i])
            return max(ans)

Log in to reply
 

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