# Python DP Solution with explanation. O(N) space and O(1) space.

• At each step there are two possibilities. Either the previous(i-1)th number was included or it was not included. We chose the one which maximizes the total sum till ith number.
So,
dp[i] = max(dp[i-1]+nums[i],0+nums[i])
Now, going back to the problem definition we need to find max subarray which will be include nums[i:j] . In order to find this , we need to look at dp[j] . As per the definition of the problem this has to be maximum sum. so max(dp) will give us the result.

``````def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0

dp = [0]*len(nums)
dp[0] = nums[0]

for i in range(1,len(nums)):
dp[i] = max(dp[i-1]+nums[i],nums[i])

return max(dp)
``````

We can further optimize the space complexity by noticing that we only need dp[i-1] to calculate dp[i] and one more variable to keep track of maximum so far.

``````def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0

cur = nums[0]
max_arr = nums[0]
for i in range(1,len(nums)):
cur = max(cur+nums[i],nums[i])
max_arr = max(cur,max_arr)

return max_arr
``````

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