# Python solution with thought process shared

• This problem has optimal sub-problems. Thus it is suitable for dynamic programming.

Assuming array sum_max stores the max of continuous subarray sum of the total array up to i but not include i. Once nums[j] is included, it may or may not change the sum. The initial (wrong) intuitive was to use
sum_max[i] = max(sum_max[i], sum_max[i-1] + nums[i])
However, this produces the largest achievable sum of this array, which does not meet the 'continuous' requirement. To meet the continuous requirement, it is important to 'restart' the subarray from i if including nums[i] changes the max sum that sum_max[i-1] is representing. Thus, the correct iteration is:
sum_max[i] = max(nums[i], sum_max[i-1] + nums[i])
That is to say,, if including nums[i] changes the optimal, reset the optimal with the value of nums[i]. However, this could reduce sum_max[i] overtime if sum_max[i-1] and nums[i] are both negative number. To avoid the optimal sum to be discarded, add the following line to keep the optimal sum that has been discovered so far.
result = max(sum_max[i], result)

Also note that sum_max[i] array is not needed despite it helps the thinking process.

class Solution(object):
def maxSubArray(self, nums):
L = len(nums)
sum_max = nums[0]
result = sum_max
for i in range(1, L):
sum_max = max(nums[i], sum_max + nums[i])
result = max(sum_max, result)
return result

• found that the indentation was removed, try to post again.
"""
class Solution(object):
def maxSubArray(self, nums):
L = len(nums)
sum_max = nums[0]
result = sum_max
for i in range(1, L):
sum_max = max(nums[i], sum_max + nums[i])
result = max(sum_max, result)
return result
"""

• Finally figured out the correct way of posting code.

``````class Solution(object):
def maxSubArray(self, nums):
L = len(nums)
sum_max = nums[0]
result = sum_max
for i in range(1, L):
sum_max = max(nums[i], sum_max + nums[i])
result = max(sum_max, result)
return result
``````

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